Submission #968074


Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

vector<int> t_parent;
vi t_ord;

template<typename T>
void wtree_getorder(const vector<vector<pair<int, T> > > &gw, int root, vector<T> &t_weight) {
	int n = (int)gw.size();
	t_parent.assign(n, -1);
	t_ord.clear();
	t_weight.assign(n, T());

	vector<int> stk; stk.push_back(root);
	while(!stk.empty()) {
		int i = stk.back(); stk.pop_back();
		t_ord.push_back(i);
		for(int j = (int)gw[i].size() - 1; j >= 0; j --) {
			int c = gw[i][j].first;
			if(t_parent[c] == -1 && c != root) {
				t_parent[c] = i;
				t_weight[c] = gw[i][j].second;
				stk.push_back(c);
			}
		}
	}
}

template<typename VertexAttr, typename EdgeAttr>
class CentroidDecomposition {
public:
	struct Vertex : VertexAttr {
		int id;

		Vertex() {}
		Vertex(int id, VertexAttr attr) : id(id), VertexAttr(attr) {}
	};

	struct VertexAndEdge : Vertex, EdgeAttr {
		VertexAndEdge() {}
		VertexAndEdge(Vertex vertex, EdgeAttr edgeAttr) : Vertex(vertex), EdgeAttr(edgeAttr) {}
	};

	struct TourEntry : VertexAndEdge {
		unsigned f;

		TourEntry() {}
		TourEntry(Vertex to, EdgeAttr edgeAttr, unsigned f) :
			VertexAndEdge(to, edgeAttr), f(f) {
		}
	};

	struct DfsEntry : VertexAndEdge {
		int px;
		DfsEntry() {}
		DfsEntry(VertexAndEdge vertexAndEdge, int px) :
			VertexAndEdge(vertexAndEdge), px(px) {
		}
	};

	void init(
		const vector<int> &t_ord, const vector<int> &t_parent,
		const vector<VertexAttr> &vertexAttrs,
		const vector<EdgeAttr> &upEdgeAttrs,
		const vector<EdgeAttr> &downEdgeAttrs) {
		int n = (int)t_ord.size();
		vector<unsigned> a(n), b(n), f(n);
		unsigned maxf = 0;
		for(int ix = n - 1; ix >= 0; -- ix) {
			int i = t_ord[ix], p = t_parent[i];
			unsigned m = b[i];
			m |= m >> 1;
			m |= m >> 2;
			m |= m >> 4;
			m |= m >> 8;
			m |= m >> 16;
			unsigned fi = ~(a[i] | m);
			fi &= ~fi + 1;
			f[i] = fi;
			if(maxf < fi)
				maxf = fi;
			unsigned S = (a[i] & ~(fi - 1)) | fi;
			if(p != -1) {
				b[p] |= a[p] & S;
				a[p] |= S;
			}
		}
		eulerTour(t_ord, t_parent, vertexAttrs, upEdgeAttrs, downEdgeAttrs, f, _tour);
		_currentLevel = 0;
		while(maxf >> 1 >> _currentLevel) ++ _currentLevel;
		_subtrees.assign(_currentLevel + 1, vector<pair<int, int> >());
		if(_currentLevel != 0) {
			int middle = 1;
			while(_tour[middle].f != maxf) ++ middle;
			std::rotate(_tour.begin() + 1, _tour.begin() + (middle + 1), _tour.end());
		}
		_subtrees[_currentLevel].assign(1, make_pair(1, (n - 1) * 2 + 1));
	}

	bool makeNextLevel() {
		if(_currentLevel == 0) return false;
		unsigned lv = 1U << (_currentLevel - 1);
		const vector<pair<int, int> > &currentSubtrees = _subtrees[_currentLevel];
		for(int si = 0; si < (int)currentSubtrees.size(); ++ si) {
			int L = currentSubtrees[si].first, R = currentSubtrees[si].second;
			int nextL = L + 1;
			unsigned nextLevel = 0;
			int nextMiddle = -1;
			for(int ix = L; ix < R; ++ ix) {
				unsigned f = _tour[ix].f;
				if(f > lv) {
					std::rotate(_tour.begin() + nextL, _tour.begin() + nextMiddle, _tour.begin() + ix);
					int k = _currentLevel;
					while(nextLevel != (1U << k)) -- k;
					_subtrees[k].push_back(make_pair(nextL, ix));
					nextL = ix + 2;
					nextLevel = 0;
					nextMiddle = -1;
				} else if(nextLevel < f) {
					nextLevel = f;
					nextMiddle = ix + 1;
				}
			}
		}
		-- _currentLevel;
		return true;
	}

	int currentLevel() const { return _currentLevel; }
	int numCurrentSubtrees() const { return (int)_subtrees[_currentLevel].size(); }

	void getDfsOrder(int si, vector<DfsEntry> &ord, vector<pair<int, int> > &tmpStack) const {
		assert(0 <= si && si < numCurrentSubtrees());
		tmpStack.resize(_tour.size() / 2 + 2);
		pair<int, int> subtree = _subtrees[_currentLevel][si];
		int L = subtree.first, R = subtree.second;
		ord.clear();
		ord.push_back(DfsEntry(VertexAndEdge((Vertex)(VertexAndEdge)_tour[R - 1], EdgeAttr()), -1));
		int sp = 1;
		tmpStack[0] = make_pair(-1, -1);
		tmpStack[sp ++] = make_pair(_tour[R - 1].id, 0);
		for(int tx = L; tx < R - 1; ++ tx) {
			int id = _tour[tx].id;
			if(id == tmpStack[sp - 2].first) {
				-- sp;
			} else {
				int px = tmpStack[sp - 1].second;
				int ix = (int)ord.size();
				tmpStack[sp ++] = make_pair(id, ix);
				ord.push_back(DfsEntry(_tour[tx], px));
			}
		}
	}

	void debugShow() const {
		cerr << "level " << _currentLevel << ":\n";
		const vector<pair<int, int> > &currentSubtrees = _subtrees[_currentLevel];
		for(int si = 0; si < (int)currentSubtrees.size(); ++ si) {
			int L = currentSubtrees[si].first, R = currentSubtrees[si].second;
			if(L == R)
				cerr << "[" << (L == 0 ? 0 : _tour[L - 1].id) << "]";
			for(int ix = L; ix < R; ++ ix) {
				cerr << _tour[ix].id << ", ";
			}
			cerr << '\n';
		}
	}

private:
	static void eulerTour(
		const vector<int> &t_ord, const vector<int> &t_parent,
		const vector<VertexAttr> &vertexAttrs,
		const vector<EdgeAttr> &upEdgeAttrs,
		const vector<EdgeAttr> &downEdgeAttrs,
		const vector<unsigned> &f, vector<TourEntry> &tour) {
		int n = (int)t_ord.size();
		tour.clear(); tour.reserve((n - 1) * 2 + 1);
		int root = t_ord[0], i = root;
		//a kind of sentinel
		tour.push_back(TourEntry(Vertex(root, vertexAttrs[root]), EdgeAttr(), f[root]));
		for(int ix = 1; ix <= n; ++ ix) {
			int p = ix < n ? t_parent[t_ord[ix]] : root;
			while(i != p) {
				EdgeAttr w = upEdgeAttrs[i];
				i = t_parent[i];
				tour.push_back(TourEntry(Vertex(i, vertexAttrs[i]), w, f[i]));
			}
			if(ix < n) {
				i = t_ord[ix];
				EdgeAttr w = downEdgeAttrs[i];
				tour.push_back(TourEntry(Vertex(i, vertexAttrs[i]), w, f[i]));
			}
		}
		assert(tour.size() == (n - 1) * 2 + 1);
	}

private:
	int _currentLevel;
	vector<TourEntry> _tour;
	vector<vector<pair<int, int> > > _subtrees;
};

struct VertexAttr {};
struct EdgeAttr { int weight; };

struct CntSum {
	CntSum() : cnt(0), sum(0) {}
	CntSum &operator+=(const CntSum &that) {
		cnt += that.cnt, sum += that.sum;
		return *this;
	}
	CntSum &operator-=(const CntSum &that) {
		cnt -= that.cnt, sum -= that.sum;
		return *this;
	}
	ll cnt, sum;
};

int main() {
	int N; int X;
	while(~scanf("%d%d", &N, &X)) {
		vector<vector<int> > g(N);
		vector<vector<pair<int, EdgeAttr> > > gw(N);
		for(int i = 0; i < N - 1; ++ i) {
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w), -- u, -- v;
			g[u].push_back(v);
			g[v].push_back(u);
			gw[u].push_back(make_pair(v, EdgeAttr{ w }));
			gw[v].push_back(make_pair(u, EdgeAttr{ w }));
		}

		vector<int> seq;
		auto solve = [&seq, X](vector<int>::const_iterator begin, vector<int>::const_iterator end) -> CntSum {
			int n = (int)(end - begin);
			seq.clear();
			seq.reserve(n);
			for(auto it = begin; it != end; ++ it)
				seq.push_back(*it);
			sort(seq.begin(), seq.end());
			CntSum res;
			ll cursum = 0;
			for(int i = n - 1, j = 0; i >= 0; -- i) {
				int x = seq[i];
				for(; j != n && x + seq[j] < X; ++ j)
					cursum += seq[j];
				res.cnt += j;
				res.sum += cursum + (ll)x * j;
			}
			for(int x : seq) if(x * 2 < X) {
				-- res.cnt;
				res.sum -= x * 2;
			}
			assert(res.cnt % 2 == 0 && res.sum % 2 == 0);
			res.cnt /= 2;
			res.sum /= 2;
			return res;
		};

		vector<EdgeAttr> weight;
		wtree_getorder(gw, 0, weight);
		CentroidDecomposition<VertexAttr, EdgeAttr> cd;
		cd.init(t_ord, t_parent, vector<VertexAttr>(N), weight, weight);
		CntSum notX;
		do {
			vector<pair<int, int>> tmpStack;
			vector<CentroidDecomposition<VertexAttr, EdgeAttr>::DfsEntry> ord;
			vector<int> sums;
			vi bounds;
			rep(si, cd.numCurrentSubtrees()) {
				cd.getDfsOrder(si, ord, tmpStack);
				sums.resize(ord.size());
				sums[0] = 0;
				bounds.clear();
				bounds.push_back(0);
				ll cnt = 0;
				for(int ix = 1; ix < (int)ord.size(); ++ ix) {
					const auto &entry = ord[ix];
					sums[ix] = sums[entry.px] + entry.weight;
					if(entry.px == 0)
						bounds.push_back(ix);
				}
				bounds.push_back((int)ord.size());
				notX += solve(sums.begin(), sums.end());
				rep(bi, bounds.size() - 1)
					notX -= solve(sums.begin() + bounds[bi], sums.begin() + bounds[bi + 1]);
			}
		} while(cd.makeNextLevel());

		vector<int> minadj(N, INF);
		rep(i, N) for(auto &&e : gw[i])
			amin(minadj[i], e.second.weight);
		for(int ix = 1; ix < (int)t_ord.size(); ++ ix) {
			int i = t_ord[ix], p = t_parent[i], w = weight[i].weight;
			if(X <= w) {
				int mind = w;
				amin(mind, minadj[i] + X);
				amin(mind, minadj[p] + X);
				if(g[i].size() + g[p].size() != N)
					amin(mind, X * 2);
				if(N >= 4 && g[i].size() != N - 1 && g[p].size() != N - 1)
					amin(mind, X * 3);
				++ notX.cnt;
				notX.sum += mind;
			}
		}
		ll xCnt = (ll)N * (N - 1) / 2 - notX.cnt;
		ll ans = 0;
		ans += notX.sum;
		ans += xCnt * X;
		printf("%lld\n", ans);
	}
	return 0;
}

Submission Info

Submission Time
Task D - 道路網
User anta
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 9536 Byte
Status AC
Exec Time 216 ms
Memory 19868 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:233:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d", &u, &v, &w), -- u, -- v;
                                           ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 2
AC × 46
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt
All 00_example_01.txt, 00_example_02.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 20_k-ary_01.txt, 20_k-ary_02.txt, 20_k-ary_03.txt, 20_k-ary_04.txt, 20_k-ary_05.txt, 20_k-ary_06.txt, 20_k-ary_07.txt, 20_k-ary_08.txt, 20_k-ary_09.txt, 20_k-ary_10.txt, 30_star_01.txt, 30_star_02.txt, 30_star_03.txt, 30_star_04.txt, 30_star_05.txt, 40_pseudostar_01.txt, 40_pseudostar_02.txt, 40_pseudostar_04.txt, 40_pseudostar_05.txt, 40_pseudostar_06.txt, 50_line_01.txt, 50_line_02.txt, 50_line_03.txt, 60_max_01.txt, 60_max_02.txt, 60_max_03.txt, 60_max_04.txt, 70_hand_01.txt, 70_hand_02.txt, 71_hand_01.txt, 72_hand_01.txt, 80_kill2X_01.txt, 80_kill2X_02.txt, 80_kill2X_03.txt, 80_kill2X_04.txt, 80_kill2X_05.txt, 80_kill2X_06.txt, 80_kill2X_07.txt, 80_kill2X_08.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 3 ms 256 KB
00_example_02.txt AC 3 ms 256 KB
10_rand_01.txt AC 3 ms 256 KB
10_rand_02.txt AC 3 ms 256 KB
10_rand_03.txt AC 3 ms 256 KB
10_rand_04.txt AC 3 ms 384 KB
10_rand_05.txt AC 3 ms 384 KB
20_k-ary_01.txt AC 215 ms 18368 KB
20_k-ary_02.txt AC 214 ms 18368 KB
20_k-ary_03.txt AC 216 ms 18368 KB
20_k-ary_04.txt AC 160 ms 19612 KB
20_k-ary_05.txt AC 137 ms 19868 KB
20_k-ary_06.txt AC 106 ms 19480 KB
20_k-ary_07.txt AC 99 ms 19864 KB
20_k-ary_08.txt AC 97 ms 19480 KB
20_k-ary_09.txt AC 106 ms 19096 KB
20_k-ary_10.txt AC 97 ms 19116 KB
30_star_01.txt AC 98 ms 19564 KB
30_star_02.txt AC 96 ms 19564 KB
30_star_03.txt AC 98 ms 19564 KB
30_star_04.txt AC 97 ms 19564 KB
30_star_05.txt AC 96 ms 19564 KB
40_pseudostar_01.txt AC 97 ms 19564 KB
40_pseudostar_02.txt AC 102 ms 19436 KB
40_pseudostar_04.txt AC 101 ms 19636 KB
40_pseudostar_05.txt AC 105 ms 19440 KB
40_pseudostar_06.txt AC 105 ms 19380 KB
50_line_01.txt AC 195 ms 17564 KB
50_line_02.txt AC 193 ms 17564 KB
50_line_03.txt AC 193 ms 17564 KB
60_max_01.txt AC 193 ms 18200 KB
60_max_02.txt AC 204 ms 19096 KB
60_max_03.txt AC 173 ms 18328 KB
60_max_04.txt AC 185 ms 18200 KB
70_hand_01.txt AC 3 ms 256 KB
70_hand_02.txt AC 3 ms 256 KB
71_hand_01.txt AC 176 ms 18840 KB
72_hand_01.txt AC 188 ms 17564 KB
80_kill2X_01.txt AC 97 ms 19564 KB
80_kill2X_02.txt AC 98 ms 19564 KB
80_kill2X_03.txt AC 98 ms 19564 KB
80_kill2X_04.txt AC 98 ms 19564 KB
80_kill2X_05.txt AC 101 ms 19440 KB
80_kill2X_06.txt AC 98 ms 19380 KB
80_kill2X_07.txt AC 97 ms 19288 KB
80_kill2X_08.txt AC 108 ms 19508 KB