Submission #249943

#	Time	Username	Problem	Language	Result	Execution time	Memory
249943		mieszko11b	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	2079 ms	36600 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;

struct SegmentSegmentTree {
	int lv;
	vector<pll> d;
	vector<ll> ins;
	
	//1..n
	SegmentSegmentTree(int n) {
		lv = 2;
		while(lv < n + 2)
			lv *= 2;
		d.resize(2 * lv + 3, {-1e18, 0});
		ins.resize(2 * lv + 3);
		for(int i = 1 ; i <= lv ; i++)
			d[lv + i - 1].Y = i;
	}
	
	void initv(int i, ll x) {
		d[lv + i - 1].X = x;
	}
	
	void process_init() {
		for(int i = lv - 1 ; i >= 1 ; i--)
			d[i] = max(d[2 * i], d[2 * i + 1]);
	}
	
	void insert(int a, int b, int l, int r, int w, ll x) {
		if(a > r || b < l || l > r)
			return ;
		if(a <= l && r <= b) {
			ins[w] += x;
			d[w].X += x;
			return; 
		}
		
		insert(a, b, l, (l + r) / 2, 2 * w, x);
		insert(a, b, (l + r) / 2 + 1, r, 2 * w + 1, x);
		d[w] = max(d[2 * w], d[2 * w + 1]);
		d[w].X += ins[w];
	}
	
	void insert(int a, int b, ll x) {
		insert(a, b, 1, lv, 1, x);
	}
	
	pll query(int a, int b, int l, int r, int w) {
		if(a > r || b < l || l > r)
			return {-1e18, 0};
		if(a <= l && r <= b)
			return d[w];
		
		pll p1 = query(a, b, l, (l + r) / 2, 2 * w);
		pll p2 = query(a, b, (l + r) / 2 + 1, r, 2 * w + 1);
		p1 = max(p1, p2);
		p1.X += ins[w];
		return p1;
	}
	
	pll query(int a, int b) {
		return query(a, b, 1, lv, 1);
	}
};

int n, q;
ll w;
vector<pll> G[100007];
ii E[100007];
ll ecost[100007];
int p[100007], sz[100007];
int in[100007], out[100007];
int rein[100007];
int nxt_num = 1;
int first[100007];
SegmentSegmentTree paths(100007);
SegmentSegmentTree subtrees(100007);

void dfs(int w) {
	sz[w] = 1;
	for(auto u : G[w]) {
		if(u.X != p[w]) {
			p[u.X] = w;
			dfs(u.X);
			sz[w] += sz[u.X];
		}
	}
}

ll dfs2(int w, ll dist) {
	for(auto &u : G[w])
		if(sz[u.X] > sz[G[w][0].X])	
			swap(u, G[w][0]);
			
	in[w] = out[w] = nxt_num++;
	rein[in[w]] = w;
	
	subtrees.initv(in[w], dist);

	ll maxdist = dist, maxall = dist;
	for(auto u : G[w]) {
		if(u == G[w][0])
			first[u.X] = first[w];
		else
			first[u.X] = u.X;
		if(u != G[w][0])
			maxdist = max(maxdist, dfs2(u.X, dist + u.Y));
		else
			maxall = max(maxall, dfs2(u.X, dist + u.Y));
		out[w] = out[u.X];
	}
	
	//~ cout << w << " " << maxdist << endl;
	
	maxall = max(maxall, maxdist);
	paths.initv(in[w], maxdist - 2LL * dist);
	
	return maxall;
}

ll longest_path() {
	auto q = subtrees.query(1, n);
	int w = rein[q.Y], pre = 0;
	ll dw = q.X;

	//~ cout << dw << " " << w << endl;

	ll res = 0;
	while(w) {
		if(!pre || first[pre] == first[w]) {
			res = max(res, paths.query(in[first[w]], in[w]).X + dw);
			//~ cout << in[first[w]] << " " << in[w] << " " << w << " " << res << " " << paths.query(in[first[w]], in[w]).X << endl;
			pre = first[w];
			w = p[first[w]];
		} else {
			ll pdist = subtrees.query(in[w], in[w]).X;
			res = max(res, subtrees.query(in[w], in[pre] - 1).X + dw - 2LL * pdist);
									//~ cout << w << " " << pre << " " << pdist << " " << dw << " " << res << endl;
			res = max(res, subtrees.query(out[pre] + 1, out[w]).X + dw - 2LL * pdist);
						//~ cout << w << " " << pre << " " << pdist << " " << dw << " " << res << endl;
			pre = w;
			w = p[w];
		}
	}
	
	
	return res;
}

void change_edge(int e, ll x) {
	//~ cout << e << " " << x << endl;
	
	int w = E[e].X;
	int u = E[e].Y;
	if(in[w] > in[u])
		swap(w, u);
		
	ll delta = x - ecost[e];
	ecost[e] = x;
		
	paths.insert(in[u], out[u], -delta);
	subtrees.insert(in[u], out[u], delta);
	
	w = p[first[u]];
	
	//~ cout << w << " " << u << endl;
	
	while(w) {
		//~ cout << w << endl;
		ll actv = paths.query(in[w], in[w]).X;
		ll pdist = subtrees.query(in[w], in[w]).X;
		ll newv = subtrees.query(out[G[w][0].X] + 1, out[w]).X - 2LL * pdist;
		
		//~ cout << actv << " " << newv << endl;
		
		paths.insert(in[w], in[w], newv - actv);
		w = p[first[w]];
	}
}

int main() {
	scanf("%d%d%lld", &n, &q, &w);
	for(int i = 1 ; i < n ; i++) {
		int a, b;
		ll c;
		scanf("%d%d%lld", &a, &b, &c);
		G[a].emplace_back(b, c);
		G[b].emplace_back(a, c);
		ecost[i] = c;
		E[i] = {a, b};
	}
	
	dfs(1);
	for(int i = 1 ; i <= n ; i++) {
		for(int j = 0 ; j < G[i].size() ; j++) {
			if(G[i][j].X == p[i]) {
				G[i].erase(G[i].begin() + j);
				break;
			}
		}
	}
	
	first[1] = 1;
	dfs2(1, 0);
	subtrees.process_init();
	paths.process_init();

	//~ for(int i = 1 ; i <= n ; i++)
		//~ cout << i << " "<< first[i] << endl;

	//~ cout << longest_path() << endl;

	//~ cout << paths.query(1, 1).X << endl;

		
		//~ for(int i = 1 ; i <= n ; i++)
			//~ cout << i << " " << in[i] << " " << paths.query(in[i], in[i]).X << " " << paths.query(in[i], in[i]).Y << endl;

	ll last = 0;
	while(q--) {
		ll d, e;
		scanf("%lld%lld", &d, &e);
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		
		change_edge(d + 1, e);
	
		
		//~ for(int i = 1 ; i <= n ; i++)
			//~ cout << i << " " << in[i] << " " << paths.query(in[i], in[i]).X << " " << paths.query(in[i], in[i]).Y << endl;
		
		printf("%lld\n", last = longest_path());
	}
	
	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:203:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < G[i].size() ; j++) {
                   ~~^~~~~~~~~~~~~
diameter.cpp:190:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &n, &q, &w);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:194:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:230:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &d, &e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

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