Submission #604804

#	Time	Username	Problem	Language	Result	Execution time	Memory
604804		enter_hedgehog_poly	Dynamic Diameter (CEOI19_diameter)	C++11	49 / 100	5007 ms	158528 KiB

diameter

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define N 100010

inline ll log2ceil(ll n) { return 64 - __builtin_clzll(n); }

struct Edge {
	ll w;
	int a, b;

	Edge() {}

	Edge(ll w, int a, int b) : w(w), a(a), b(b) {}

	int other(int x) const { return x == a ? b: a; }
};

class SegmentTree {
public:
	void init(int size) {
		tree_size = 1 << log2ceil(size + 1);
		tree = new ll[tree_size * 2];
		lazy = new ll[tree_size * 2];

		fill(tree, tree + 2*tree_size - 1, 0);
		fill(lazy, lazy + 2*tree_size - 1, 0);
	}

	ll add(int l, int r, ll v) {
		ql = l + tree_size;
		qr = r + tree_size;
		qv = v;
		return _add(1, tree_size, 2*tree_size - 1);
	}

	ll get(int l, int r) {
		ql = l + tree_size;
		qr = r + tree_size;
		return _get(1, tree_size, 2*tree_size - 1);
	}
private:
	void push(int n) {
		tree[n] += lazy[n];
		if(n < tree_size) {

			lazy[2 * n] += lazy[n];
			lazy[2 * n + 1] += lazy[n];
		}
		lazy[n] = 0;
	}

	ll _add(int n, int lms, int rms) {
		push(n);
		if(ql <= lms && rms <= qr) {
			tree[n] += qv;
			if(n < tree_size) {
				lazy[2 * n] += qv;
				lazy[2 * n + 1] += qv;
			}
		} else if(lms <= qr && ql <= rms) {
			int m = (lms + rms )>> 1;
			tree[n] = max(_add(2 * n, lms, m), _add(2 * n + 1, m + 1, rms));
		}
		return tree[n];
	}

	ll _get(int n, int lms, int rms) {
		push(n);
		if (ql <= lms && rms <= qr) {
			return tree[n];
		} else if (lms <= qr && ql <= rms) {
			int m = (lms + rms) >> 1;
			return max(_get(2 * n, lms, m), _get(2 * n + 1, m + 1, rms));
		}
		return 0;
	}

	ll ql, qr, qv;
	ll *tree = 0;
	ll *lazy = 0;
	int tree_size = 0;
};

vector<Edge*> graf[N];
Edge edges[N];

int centroid[N];
int cdepth[N];
int depth[18][N];
int d_root[18][N]; //vertex below centroid at given level that n belongs to
int c_root[18][N]; //centroid at given level that n belngs to

int c_tree_size[N]; //size of sub tree with root n, a.k.a the last split

int pre[18][N], post[18][N];

int calc_size_and_number(int n, int f, int cd, int p, int d);
int decompose(int n, int f, int d) ;

multiset<ll, greater<ll>> centroid_subtree_depths[N];

void erase(multiset<ll, greater<ll>> &st, ll val) {
	auto it = st.find(val);
	if(it != st.end()) st.erase(it);
}

SegmentTree trees[N];

int main() {
	ll n, q, w;
	cin >> n >> q >> w;

	for(int i = 0; i < n - 1; i++) {
		scanf("%d%d%lld", &edges[i].a, &edges[i].b, &edges[i].w);
		graf[edges[i].a].push_back(edges + i);
		graf[edges[i].b].push_back(edges + i);
	}

	if(n == 2) {
		ll last = 0;
		while(q--) {
			int edge_id;
			ll new_weight;
			scanf("%d%lld", &edge_id, &new_weight);
			last = new_weight = (new_weight + last) % w;
			printf("%lld\n", new_weight);
		}
		return 0;
	}

	auto t1 = chrono::high_resolution_clock::now();

	calc_size_and_number(1, 0, 0, 1, 1);

	int r = decompose(1, 0, 1);
	centroid[r] = 0;

	auto t2 = chrono::high_resolution_clock::now();

	for(int i = 1; i <= n; i++)
		trees[i].init(c_tree_size[i]);

	for(auto i = 0; i < n - 1; i++) {
		Edge e = edges[i];

		for(int j = 1; depth[j][e.a] && depth[j][e.b]; j++) {
			int x = depth[j][e.a] < depth[j][e.b] ? e.b : e.a;
			trees[c_root[j][x]].add(pre[j][x], post[j][x], e.w);
		}
	}

	multiset<ll, greater<ll>> result;

	auto t3 = chrono::high_resolution_clock::now();

	for(auto v = 1; v <= n; v++) {
		for(auto i: graf[v]) {
			if(cdepth[i->other(v)] < cdepth[v]) continue;
			ll x = trees[v].get(pre[cdepth[v]][i->other(v)], post[cdepth[v]][i->other(v)]);
			centroid_subtree_depths[v].insert(x);
		}

		if(centroid_subtree_depths[v].size() > 1)
			result.insert(*centroid_subtree_depths[v].begin() + *++centroid_subtree_depths[v].begin());
	}

	auto t4 = chrono::high_resolution_clock::now();

//	cout << "Phse 1: " << (double)(t2 - t1).count() / 1000000.0F << "ms" << endl;
//	cout << "Phse 2: " << (double)(t3 - t2).count() / 1000000.0F << "ms" << endl;
//	cout << "Phse 3: " << (double)(t4 - t3).count() / 1000000.0F << "ms" << endl;

	//return 0;

	ll last = 0;

	int mxd = 0;

	while(q--) {
		int edge_id;
		ll new_weight;
		scanf("%d%lld", &edge_id, &new_weight);
		edge_id = (int)(((ll)edge_id + last) % (n - 1));
		new_weight = (new_weight + last) % w;
		Edge &e = edges[edge_id];
		ll delta = new_weight - e.w;

		int c = cdepth[e.a] < cdepth[e.b] ? e.a : e.b;

		int cnt = 0;

		while(c) {
			if(centroid_subtree_depths[c].size() > 1) erase(result,*centroid_subtree_depths[c].begin() + *++centroid_subtree_depths[c].begin());
			int d = cdepth[c];

			int v = depth[d][e.a] < depth[d][e.b] ? e.b : e.a;

			/*qt = d;
			ql = pre[d][d_root[d][v]] + TS;
			qr = post[d][d_root[d][v]] + TS;
			ll x = get_max(1, TS, 2*TS - 1);*/
			ll x = trees[c].get(pre[d][d_root[d][v]], post[d][d_root[d][v]]);
			erase(centroid_subtree_depths[c], x);

			/*ql = pre[d][v] + TS;
			qr = post[d][v] + TS;
			qv = new_weight - e.w;*/
			//add_tree(1, TS, 2*TS - 1);
			trees[c].add(pre[d][v], post[d][v], delta);

			//ql = pre[d][d_root[d][v]] + TS;
			//qr = post[d][d_root[d][v]] + TS;
			//centroid_subtree_depths[c].insert(get_max(1, TS, 2*TS - 1));
			x = trees[c].get(pre[d][d_root[d][v]], post[d][d_root[d][v]]);
			centroid_subtree_depths[c].insert(x);

			if(centroid_subtree_depths[c].size() > 1) result.insert(*centroid_subtree_depths[c].begin() + *++centroid_subtree_depths[c].begin());

			c = centroid[c];
			cnt++;
		}

		e.w = new_weight;

		last = *result.begin();
		printf("%lld\n", last);
	}

	return 0;
}

int sub_tree_size[N];

int calc_size_and_number(int n, int f, int cd, int p, int d) {
	sub_tree_size[n] = 0;
	post[cd][n] = pre[cd][n] = p;
	depth[cd][n] = d;
	for(auto i: graf[n]) {
		if(i->other(n) == f || centroid[i->other(n)]) continue;
		p = calc_size_and_number(i->other(n), n, cd, p + 1, d + 1);
		sub_tree_size[n] += sub_tree_size[i->other(n)] + 1;
	}
	return post[cd][n] = p;
}

int find_centroid(int n, int root, int size, int f) {
	for (auto i: graf[n]) {
		if (i->other(n) == f || centroid[i->other(n)]) continue;
		if (sub_tree_size[i->other(n)] >= size / 2)
			return find_centroid(i->other(n), root, size, n);
	}
	return n;
}

void mark_droot(int n, int f, int cd, int r, int c) {
	d_root[cd][n] = r;
	c_root[cd][n] = c;
	for(auto i: graf[n]) {
		if(i->other(n) == f || centroid[i->other(n)]) continue;
		mark_droot(i->other(n), n, cd, r, c);
	}
}

int decompose(int n, int f, int d) {
	int r = find_centroid(n, f, sub_tree_size[n] + 1, 0);
	centroid[r] = f ? f: r;
	cdepth[r] = d;
	c_tree_size[r] = calc_size_and_number(r, 0, d, 1, 1);
	for(auto i: graf[r]) {
		if(centroid[i->other(r)]) continue;
		mark_droot(i->other(r), r, d, i->other(r), r);
		decompose(i->other(r), r, d + 1);
	}
	return r;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:134:7: warning: variable 't1' set but not used [-Wunused-but-set-variable]
  134 |  auto t1 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:141:7: warning: variable 't2' set but not used [-Wunused-but-set-variable]
  141 |  auto t2 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:157:7: warning: variable 't3' set but not used [-Wunused-but-set-variable]
  157 |  auto t3 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:170:7: warning: variable 't4' set but not used [-Wunused-but-set-variable]
  170 |  auto t4 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:180:6: warning: unused variable 'mxd' [-Wunused-variable]
  180 |  int mxd = 0;
      |      ^~~
diameter.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |   scanf("%d%d%lld", &edges[i].a, &edges[i].b, &edges[i].w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:127:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |    scanf("%d%lld", &edge_id, &new_weight);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:185:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |   scanf("%d%lld", &edge_id, &new_weight);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27