Submission #676497

#	Time	Username	Problem	Language	Result	Execution time	Memory
676497		penguin133	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	472 ms	73784 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#define getchar_unlocked getchar_nolock

int n, q, w;
int fst[100005], lst[100005], eu[200005], S[100005], dist[100005];
pi par[100005];
int cnt = 1, in = 1;
vector<pi>v[100005];
void dfs(int x, pi p, int cur){
	fst[x] = lst[x] = in;
	S[x] = cnt++;
	eu[in++] = x;
	par[x] = p;
	dist[x] = cur;
	for(auto [i, j] : v[x]){
		if(i == p.fi)continue;
		dfs(i, {x, j}, cur + j);
		lst[x] = in;
		eu[in++] = x;
	}
}

struct node{
	int s, e, m;
	int x, y, z, xy, yz, xyz, lazy;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)>>1;
		x = y = z = xy = yz = xyz = lazy = 0;
		if(s != e)l = new node(s, m), r= new node(m+1, e);
		else xy = yz = xyz = -1e18;
	}
	void propo(){
		if(lazy){
			x += lazy;
			y += 2 * lazy;
			z += lazy;
			xy -= lazy;
			yz -= lazy;
			if(s != e)l->lazy += lazy, r->lazy += lazy;
			lazy = 0;
		}
	}
	void upd(int a, int b, int c){
		if(s == a && b == e)lazy += c;
		else{
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b ,c);
			l->propo(), r->propo();
			x = max(l->x, r->x);
			y = min(l->y, r->y);
			z = max(l->z, r->z);
			xy = max({l->xy, r->xy, l->x - r->y});
			yz = max({l->yz, r->yz, -l->y + r->z});
			xyz = max({l->xyz, r->xyz, l->xy + r->z, l->x + r->yz});
		}
	}
	void dbg(){
		cout << s << " " << e << " " << x << " " << y << " " << z << " " << xy << " " << yz << " " << xyz << '\n';
		if(s == e)return;
		l->dbg();
		r->dbg(); 
	}
}*root;

pii A[100005];

void solve(){
	cin >> n >> q >> w;
	for(int i=1;i<n;i++){
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({b, c});
		v[b].push_back({a, c});
		A[i] = {a, {b, c}};
	}
	
	dfs(1, {-1, -1}, 0);
	root = new node(1, in);
	for(int i=1;i<in;i++)root->upd(i, i, dist[eu[i]]);
	//cout << root->xyz << '\n';
	//root->dbg();
	//for(int i=1;i<in;i++)cout << eu[i] << ' ' << dist[eu[i]] << '\n';
	int lastans = 0;
	while(q--){
		int x, y;
		cin >> x >> y;
		x = (x + lastans)%(n - 1);
		y = (y + lastans)%w;
		int tmp = A[x+1].fi;
		if(par[tmp].fi != A[x+1].se.fi)tmp = A[x+1].se.fi;
		//cerr << tmp << " " << fst[tmp] << " " << lst[tmp] << " " << par[tmp].fi << " " << par[tmp].se << '\n';
		root->upd(fst[tmp], lst[tmp], y - par[tmp].se);
		//cerr << "died\n";
		par[tmp].se = y;
		root->propo();
		lastans = root->xyz;
		cout << lastans << '\n';
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

diameter.cpp:110:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  110 | main(){
      | ^~~~

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