Submission #604963

#	Time	Username	Problem	Language	Result	Execution time	Memory
604963		enter_hedgehog_poly	Dynamic Diameter (CEOI19_diameter)	C++11	100 / 100	3799 ms	153320 KiB

diameter

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define N 100010

inline int log2ceil(int n) { return 32 - __builtin_clz(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_log = log2ceil(size + 1);
		tree_size = 1 << tree_size_log;
		tree = new ll[tree_size << 1];
		lazy = new ll[tree_size << 1];

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

	void add(int l, int r, ll v) {
		l += tree_size;
		r += tree_size + 1; //one over r
		int xl = l, xr = r;
		while(l < r) {
			if(l & 1) add_lazy(l++, v);
			if(r & 1) add_lazy(--r, v);
			l >>= 1;
			r >>= 1;
		}

		pull(xl);
		pull(xr - 1);
	}

	ll get(int l, int r) {
		l += tree_size;
		r += tree_size + 1;
		push(l);
		push(r - 1);

		ll res = 0;
		while(l < r) {
			if (l & 1) res = max(res, tree[l++]);
			if (r & 1) res = max(tree[--r], res);
			l >>= 1;
			r >>= 1;
		}
		return res;
	}
private:
	inline void add_lazy(int n, ll v) {
		tree[n] += v;
		if(n < tree_size) lazy[n] += v;
	}

	inline void pull(int n) {
		while((n >>= 1)) {
			tree[n] = max(tree[n << 1], tree[n << 1 | 1]) + lazy[n];
		}
	}

	inline void push(int n) {
		for(int h = tree_size_log; h ^ 0; --h) {
			int i = n >> h;
			if(lazy[i]) {
				add_lazy(i<<1, lazy[i]);
				add_lazy(i<<1 | 1, lazy[i]);
				lazy[i] = 0;
			}
		}
	}

	ll *tree = 0;
	ll *lazy = 0;
	int tree_size = 0, tree_size_log = 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 belongs to

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(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);
		}
	}
	//putchar('A');
	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;

	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;

			ll x = trees[c].get(pre[d][d_root[d][v]], post[d][d_root[d][v]]);
			erase(centroid_subtree_depths[c], x);

			trees[c].add(pre[d][v], post[d][v], delta);

			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_roots(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_roots(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;
	trees[r].init(calc_size_and_number(r, 0, d, 1, 1));
	for(auto i: graf[r]) {
		if(centroid[i->other(r)]) continue;
		mark_roots(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:118:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  118 |  for(int i = 0; i ^ n - 1; ++i) {
      |                     ~~^~~
diameter.cpp:136:7: warning: variable 't1' set but not used [-Wunused-but-set-variable]
  136 |  auto t1 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:143:7: warning: variable 't2' set but not used [-Wunused-but-set-variable]
  143 |  auto t2 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:156:7: warning: variable 't3' set but not used [-Wunused-but-set-variable]
  156 |  auto t3 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:169:7: warning: variable 't4' set but not used [-Wunused-but-set-variable]
  169 |  auto t4 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   scanf("%d%d%lld", &edges[i].a, &edges[i].b, &edges[i].w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:129:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |    scanf("%d%lld", &edge_id, &new_weight);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:182:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |   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: 24 / 24
• Subtask 6: 27 / 27