Submission #604197

#	Time	Username	Problem	Language	Result	Execution time	Memory
604197		enter_hedgehog_poly	Dynamic Diameter (CEOI19_diameter)	C++11	49 / 100	5099 ms	102100 KiB

diameter

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define N 100010

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; }
};

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

int centroid[N];
int cdepth[N];
int depth[18][N];
int droot[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);
}

const int tree_size = 1 << 17;
//#define TS (tree_size >> min((qt - 1), 5))
#define TS tree_size
ll tree[18][2*tree_size];
ll lazy[18][2*tree_size];

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

int ql, qr, qt;
ll qv;

ll add_tree(int n, int lms, int rms);
ll get_max(int n, int lms, int rms);

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];
		qv = e.w;

		for(int j = 1; j <= 18; j++) {
			if(!depth[j][e.a] || !depth[j][e.b]) break;
			int x = depth[j][e.a] < depth[j][e.b] ? e.b : e.a;
			qt = j;
			ql = TS + pre[j][x];
			qr = TS + post[j][x];
			add_tree(1, TS, 2*TS - 1);
		}
	}

	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;
			qt = cdepth[v];
			ql = pre[cdepth[v]][i->other(v)] + TS;
			qr = post[cdepth[v]][i->other(v)] + TS;
			ll x = get_max(1, TS, 2*TS - 1);
			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];
		qv = 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][droot[d][v]] + TS;
			qr = post[d][droot[d][v]] + TS;
			ll x = get_max(1, TS, 2*TS - 1);

			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);

			ql = pre[d][droot[d][v]] + TS;
			qr = post[d][droot[d][v]] + TS;

			centroid_subtree_depths[c].insert(get_max(1, TS, 2*TS - 1));

			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();
		//cout << cnt << endl;
		//mxd = max(mxd, cnt);
		printf("%lld\n", last);
	}

	//cout << mxd << endl;

	return 0;
}

void push_lazy(int t, int n) {
	tree[t][n] += lazy[t][n];
	if(n < TS) {
		lazy[t][2 * n] += lazy[t][n];
		lazy[t][2 * n + 1] += lazy[t][n];
	}
	lazy[t][n] = 0;
}

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

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

int sub_tree_size[N];
int last_num[20];

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) {
	droot[cd][n] = r;
	for(auto i: graf[n]) {
		if(i->other(n) == f || centroid[i->other(n)]) continue;
		mark_droot(i->other(n), n, cd, r);
	}
}

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;
	last_num[d] = calc_size_and_number(r, 0, d, ++last_num[d], 1);
	for(auto i: graf[r]) {
		if(centroid[i->other(r)]) continue;
		mark_droot(i->other(r), r, d, i->other(r));
		decompose(i->other(r), r, d + 1);
	}
	return r;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:74:7: warning: variable 't1' set but not used [-Wunused-but-set-variable]
   74 |  auto t1 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:81:7: warning: variable 't2' set but not used [-Wunused-but-set-variable]
   81 |  auto t2 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:99:7: warning: variable 't3' set but not used [-Wunused-but-set-variable]
   99 |  auto t3 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:115:7: warning: variable 't4' set but not used [-Wunused-but-set-variable]
  115 |  auto t4 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:125:6: warning: unused variable 'mxd' [-Wunused-variable]
  125 |  int mxd = 0;
      |      ^~~
diameter.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d%d%lld", &edges[i].a, &edges[i].b, &edges[i].w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:67:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |    scanf("%d%lld", &edge_id, &new_weight);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   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