Submission #1178257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178257		ByeWorld	Dynamic Diameter (CEOI19_diameter)	C++20	18 / 100	184 ms	67932 KiB

diameter

#include <bits/stdc++.h>
// #pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 2e5+10;
const int MAXA = 1e9;
const int INF = 1e18+100;
const int SQRT = 500;
const int LOG = 61;
const int MOD = 1e9+7;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
int sum(int a, int b){ a %= MOD; b %= MOD; return (a+b)%MOD; }
void chsum(int &a, int b){ a %= MOD; b %= MOD; a = (a+b)%MOD; }
void chsub(int &a, int b){ a %= MOD; b %= MOD; a = (a+MOD-b)%MOD; }
int mul(int a, int b){ a %= MOD; b %= MOD; return a*b%MOD;}
void chmul(int &a, int b){ a = a*b%MOD; }
int expo(int a, int b){
	if(b==0) return 1;
	int te = expo(a, b/2); te = mul(te, te);
	return (b%2 ? mul(te, a) : te);
}

struct node {
	int a=-INF, b=-INF, c=-INF, ab = -INF, bc = -INF, abc = -INF;
} NOL;
node make(int x){
	node ret; 
	ret.a = x; ret.b = -2*x; ret.c = x;
	return ret;
}
int val[MAXN], arr[MAXN], in[MAXN], out[MAXN], tim;
struct segtree {
	node st[4*MAXN]; int laz[4*MAXN];
	void push(int id, int lz){
		st[id].a += lz; st[id].b -= 2*lz; st[id].c += lz;
		st[id].ab -= lz; st[id].bc -= lz; 
		laz[id] += lz;
	}
	void bnc(int id, int l, int r){
		if(laz[id]==0) return;
		push(lf, laz[id]); push(rg, laz[id]);
		laz[id] = 0; 
	}
	node mrg(node X, node Y){
		if(X.a==-INF) return Y;
		if(Y.a==-INF) return X;
		node ret;
		ret.a = max(X.a, Y.a); ret.c = max(X.c, Y.c);
		ret.b = max(X.b, Y.b);
		ret.ab = max(max(X.ab, Y.ab), X.a+Y.b);
		ret.bc = max(max(X.bc, Y.bc), X.b+Y.c);
		ret.abc = max(max(X.abc,Y.abc), max(X.ab+Y.c, X.a+Y.bc));
		return ret;
	}
	void bd(int id,int l,int r){
		if(l==r){ st[id] = make(val[arr[l]]); return; }
		bd(lf,l,md); bd(rg,md+1,r);
		st[id] = mrg(st[lf], st[rg]);
	}
	node que(int id,int l,int r,int x,int y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return NOL;
		bnc(id,l,r);
		return mrg(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
	}
	node upd(int id,int l,int r,int x,int y,int p){
		if(x<=l && r<=y){
			push(id, p);
			return st[id];
		}
		if(r<x || y<l) return st[id];
		bnc(id,l,r);
		return st[id] = mrg(upd(lf,l,md,x,y,p), upd(rg,md+1,r,x,y,p));
	}
} A;

int n, q, W, par[MAXN];
int u[MAXN], v[MAXN], w[MAXN];
vector<pii> tree[MAXN], adj[MAXN];

void trav(int nw, int pa){
	in[nw] = ++tim; arr[tim] = nw;
	par[nw] = pa;
	for(auto [nx, wei] : tree[nw]){
		if(nx==pa) continue;
		adj[nw].pb({nx,wei});
		val[nx] = val[nw]+wei;
		trav(nx,nw);
		arr[++tim] = nw;
	}
	out[nw] = tim; 
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q>>W;
	for(int i=1; i<=n-1; i++){
		int x,y,we; cin>>x>>y>>we; 
		tree[x].pb({y,we}); tree[y].pb({x,we});
		u[i] = x; v[i] = y; w[i] = we;
	}
	trav(1,0);
	for(int i=1; i<=n-1; i++)
		if(par[u[i]] == v[i]) swap(u[i], v[i]);
	A.bd(1,1,tim);

	// for(int i=1; i<=tim; i++) cout << arr[i] << " \n"[i==tim];
	// for(int i=1; i<=n; i++){
	// 	cout << in[i] << ' ' << out[i] << " in\n";
	// }
	int P = 0;
	while(q--){
		int x,y; cin>>x>>y;
		x = (x+P)%(n-1)+1; y = (y+P)%W;

		int baw = v[x];
		A.upd(1,1,tim, in[baw], out[baw], y-w[x]);
		w[x] = y;
		cout << (P = A.que(1,1,tim,1,tim).abc) << '\n';
	}
}

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