Submission #836282

#	Time	Username	Problem	Language	Result	Execution time	Memory
836282		sunwukong123	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	4291 ms	274940 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define int long long 
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 100005;
const int inf=1000000500ll;
const int oo =1000000000000000000ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
/*
centroid decomposition
construct a segment tree for every tree in every layer
when updating an edge, find all layers that this edge is in
range update that subtree in that tree
range add on that subtree, then, update once, on the root's layer.
hence you can find the diameter passing through the root
by maintaining all such diameters, you can find the diameter of the whole tree
*/
int n,q,w;
int W[MAXN];
vector<pi> adj[MAXN];
int lvl[MAXN];
int sz[MAXN];
int par[MAXN];
int rt;
int st[MAXN][18], en[MAXN][18];
int ctr;
struct node {
	int s,e,m,val,lazy;
	node *l, *r;
	node (int _s, int _e){
		s=_s;e=_e;m=(s+e)/2;
		val=lazy=0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	int value(){
		if(lazy==0)return val;
		val+=lazy;
		if(s!=e){
			l->lazy+=lazy;
			r->lazy+=lazy;
		}
		lazy=0;
		return val;
	}
	void update(int x, int y, int nval){
		value();
		if(s==x&&e==y){
			lazy+=nval;
			return;
		}
		if(x>m)r->update(x,y,nval);
		else if(y<=m)l->update(x,y,nval);
		else l->update(x,m,nval), r->update(m+1,y,nval);
		val=max(l->value(),r->value()); 
	}
	int query(int x, int y){
		value();
		if(s==x&&e==y)return val;
		if(x>m)return r->query(x,y);
		else if(y<=m)return l->query(x,y);
		else return max(l->query(x,m), r->query(m+1,y));
	}

} *tree[MAXN];
vector<pi> V[MAXN];
multiset<int> L[MAXN];
void pre(int x, int p, int wei){
	for(auto v:adj[x])if(v.first!=p){
		pre(v.first,x,v.second);
	}
}
int dfs1(int x, int p){
	sz[x]=1;
	for(auto v:adj[x])if(v.first!=p){
		if(lvl[v.first] != -1)continue;
		sz[x]+=dfs1(v.first,x);
	}
	return sz[x];
}
int dfs2(int x, int tar, int p){
	for(auto v:adj[x])if(v.first!=p){
		if(lvl[v.first] != -1)continue;
		if(sz[v.first]>tar/2)return dfs2(v.first,tar,x);
	}
	return x;
}
void dfs3(int x, int p, int l){
	st[x][l]=ctr++;
	for(auto v:adj[x])if(v.first!=p){
		if(lvl[v.first] != -1)continue;
		dfs3(v.first,x,l);
	}
	en[x][l]=ctr-1;
}
multiset<int> diams;
void dfs4(int x, int p, int l, int wei){
	if(x!=rt){

		tree[rt]->update(st[x][l],en[x][l],wei);
	}
	for(auto v:adj[x])if(v.first!=p){
		if(lvl[v.first]!=-1)continue;
		dfs4(v.first,x,l,v.second);
	}
}
int getdiam(multiset<int> & s){
	if(s.empty())return 0;
	if(s.size()==1)return *s.begin();

	return *prev(s.end())+*prev(prev(s.end()));
}
void build(int x, int p, int l){

	int sz=dfs1(x,-1);
	int cent=dfs2(x,sz,l);

	if(p==-1)p=cent;
	par[cent]=p;
	lvl[cent]=l;
	rt=cent;
	ctr=0;
	dfs3(cent,-1,l);
	tree[rt]=new node(0,ctr);
	dfs4(cent,-1,l,0);
	for(auto v:adj[cent]){

		if(v.first==p)continue;
		if(lvl[v.first]!=-1)continue;

		V[cent].push_back({en[v.first][l],v.first});
	}
	
	for(auto x:V[cent]){
		int s=tree[rt]->query(st[x.second][l],en[x.second][l]);
		L[rt].insert(s);
	}
	diams.insert(getdiam(L[rt]));

	for(auto v:adj[cent])if(v.first!=p){
		if(lvl[v.first]!=-1)continue;
		build(v.first,cent,l+1);
	}
}
int last;
pi E[MAXN];

int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q >> w;
	for(int i=0;i<n-1;i++){
		int a,b,c; cin >> a >> b >> c;
		E[i]={a,b};
		W[i]=c;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}
	pre(1,-1,0);
	memset(lvl,-1,sizeof lvl);
	build(1,-1,0);
	
	while(q--){
		int d,e; cin >> d >> e;
		d=(d+last)%(n-1);
		e=(e+last)%w;


		int cc=e-W[d];
		W[d]=e;
		pair<int,int>nn=min(make_pair(lvl[E[d].first], E[d].first), make_pair(lvl[E[d].second], E[d].second));
		int X=E[d].first, Y=E[d].second;
		int y=nn.second,l=nn.first;
		while(l!=-1){

			if(st[X][l] < st[Y][l])swap(X,Y);
			//update X's subtree

			auto iter=lower_bound(V[y].begin(),V[y].end(),make_pair(st[X][l],0ll));


			int tc=iter->second;

			int lmax=tree[y]->query(st[tc][l],en[tc][l]);
			diams.erase(diams.find(getdiam(L[y])));



			L[y].erase(L[y].find(lmax));

			tree[y]->update(st[X][l],en[X][l],cc);
			lmax=tree[y]->query(st[tc][l],en[tc][l]);
			L[y].insert(lmax); 
			diams.insert(getdiam(L[y]));
			y=par[y];
			--l;
		}
		last=*prev(diams.end());
		cout<<last<<'\n';
	}
}

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