Submission #718103

#	Time	Username	Problem	Language	Result	Execution time	Memory
718103		amirhoseinfar1385	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	2211 ms	55464 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
struct yal{
	int u,v,par;
	long long w;
	yal(){
		u=v=par=w=0;
	}
	int getad(int fu){
		int ret=(fu^u^v);
		return ret;
	}
};
yal alled[maxn];
int kaf=(1<<18),lastc[maxn],vala[maxn],fake,timea=0,n,q,sz[maxn],parh[maxn],par[maxn],childh[maxn];
long long w;
vector<int>adj[maxn],adja[maxn];
pair<int,int>stf[maxn];

bool cmp(int a,int b){
	return sz[alled[a].getad(fake)]>sz[alled[b].getad(fake)];
}

void dfs1(int u,int bala=0){
	//cout<<u<<" "<<bala<<endl;
	sz[u]=1;
	par[u]=bala;
	for(auto x:adj[u]){
		int v=alled[x].getad(u);
		//cout<<u<<" "<<v<<"\n";
		if(v!=bala){
			alled[x].par=u;
			dfs1(v,u);
			adja[u].push_back(x);
			sz[u]+=sz[v];
		}
	}
	swap(adj[u],adja[u]);
	fake=u;
	sort(adj[u].begin(),adj[u].end(),cmp);
}

void calh(int u,int balah=1){
	//cout<<u<<" "<<balah<<"\n";
	timea++;
	vala[timea]=u;
	stf[u].first=timea;
	parh[u]=balah;
	//if(u==1)
//	{
	//	parh[u]=0;
	//}
	if(adj[u].size()==0){
		lastc[u]=u;
		stf[u].second=timea;
		return ;
	}
	int v=alled[adj[u][0]].getad(u);
	//cout<<u<<" "<<v<<"\n";
	calh(v,balah);
	lastc[u]=lastc[v];
	childh[u]=v;
	for(int i=1;i<(int)adj[u].size();i++){
		v=alled[adj[u][i]].getad(u);
		if(v!=par[u]){
			calh(v,v);
		}
	}
	stf[u].second=timea;
}

struct node{
	int w;
	long long maxa,lazy;
	node(){
		w=maxa=lazy=0;
	}
};

struct segment{
	node seg[(1<<19)];
	void build(int i){
		if(i>=kaf){
			seg[i].w=i-kaf;
			return ;
		}
		build((i<<1));
		build((i<<1)^1);
		seg[i].w=seg[(i<<1)].w;
	}

	node merge(node a,node b){
		a.maxa+=a.lazy;
		b.maxa+=b.lazy;
		a.lazy=0;
		b.lazy=0;
		if(a.maxa>=b.maxa){
			return a;
		}
		return b;
	}

	void calc(int i){
		if((i<<1)>=(1<<19)){
			return ;
		}
		node f=merge(seg[(i<<1)],seg[(i<<1)^1]);
		seg[i].maxa=f.maxa;
		seg[i].w=f.w;
	}

	void shift(int i){
		if((i<<1)>=(1<<19)||seg[i].lazy==0){
			return ;
		}
		seg[(i<<1)].lazy+=seg[i].lazy;
		seg[(i<<1)^1].lazy+=seg[i].lazy;
		seg[i].lazy=0;
		calc(i);
	}

	void upd(int i,int l,int r,int tl,int tr,long long w){
		if(l>r||l>tr||r<tl){
			return ;
		}
		shift(i);
		if(l>=tl&&r<=tr){
		//	cout<<l<<" "<<r<<" "<<w<<"\n";
			seg[i].lazy+=w;
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
	}

	void upd2(int i,int l,int r,int tl,int tr,long long w){
		if(l>r||l>tr||r<tl){
			return ;
		}
		shift(i);
		if(l>=tl&&r<=tr){
		//	cout<<l<<" "<<r<<" "<<w<<"\n";
			seg[i].lazy=w;
			seg[i].maxa=0;
			return ;
		}
		int m=(l+r)>>1;
		upd2((i<<1),l,m,tl,tr,w);
		upd2((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
	}


	node pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl){
			node nn;
			return nn;
		}
		shift(i);
		if(l>=tl&&r<=tr){
	//		cout<<l<<" "<<r<<" "<<seg[i].maxa<<" "<<seg[i].lazy<<" "<<seg[i].w<<" tof\n";
			return seg[i];
		}
		int m=(l+r)>>1;
		node ret=merge(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
		return ret;
	}
}seg,seg2;

void update(int i)
{
	i=parh[i];
	i=par[i];
	if(i==0){
		return ;
	}
	node l=seg.pors(1,0,kaf-1,stf[i].first,stf[childh[i]].first-1);
	node r=seg.pors(1,0,kaf-1,stf[childh[i]].second+1,stf[i].second);
	node rr=seg.pors(1,0,kaf-1,stf[i].first,stf[i].first);
	long long wtf=max(l.maxa+l.lazy,r.maxa+r.lazy)-(rr.maxa+rr.lazy)*2;
//	cout<<i<<" "<<wtf<<" "<<(rr.maxa+rr.lazy)<<" asd \n";
	seg2.upd2(1,0,kaf-1,stf[i].first,stf[i].first,wtf);
	update(i);
}

long long pors(int i,long long w){
	node boro=seg2.pors(1,0,kaf-1,stf[parh[i]].first,stf[i].first-1);
	long long ret=boro.maxa+boro.lazy+w;
	//cout<<boro.maxa+boro.lazy<<" "<<vala[boro.w]<<" "<<w<<" asda "<<endl;
//	cout<<i<<" "<<parh[i]<<" ";
	i=parh[i];
	if(par[i]==0){
		ret=max(ret,w);
	//	cout<<ret<<'\n';
		return ret;
	}	
	node l=seg.pors(1,0,kaf-1,stf[par[i]].first,stf[i].first-1);
	node r=seg.pors(1,0,kaf-1,stf[i].second+1,stf[par[i]].second);
	node rr=seg.pors(1,0,kaf-1,stf[par[i]].first,stf[par[i]].first);
	long long reta=max(l.maxa+l.lazy,r.maxa+r.lazy)-(rr.maxa+rr.lazy)*2+w;
	//cout<<ret<<" "<<reta<<"\n";
	ret=max(ret,reta);
	i=par[i];
	if(i==0){
		return ret;
	}
	ret=max(ret,pors(i,w));
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>w;
	for(int i=0;i<n-1;i++){
		cin>>alled[i].u>>alled[i].v>>alled[i].w;
		adj[alled[i].u].push_back(i);
		adj[alled[i].v].push_back(i);		
	}
	//cout<<"salam"<<endl;
	dfs1(1);
	//cout<<"salam2"<<endl;
	calh(1);
	//cout<<"salam3"<<endl;
	seg.build(1);
	seg2.build(1);
	//cout<<"salam"<<endl;
	for(int i=0;i<n-1;i++){
		int v=alled[i].getad(alled[i].par);
		//cout<<v<<" "<<alled[i].w<<"\n";
		//cout<<stf[v].first<<" "<<stf[v].second<<" "<<alled[i].w<<'\n';
		seg.upd(1,0,kaf-1,stf[v].first,stf[v].second,alled[i].w);
	}
	for(int i=1;i<=n;i++){
		if((int)adj[i].size()==0){
			continue;
		}
		node l=seg.pors(1,0,kaf-1,stf[i].first,stf[childh[i]].first-1);
		node r=seg.pors(1,0,kaf-1,stf[childh[i]].second+1,stf[i].second);
		node rr=seg.pors(1,0,kaf-1,stf[i].first,stf[i].first);
		long long wtf=max(l.maxa+l.lazy,r.maxa+r.lazy)-(rr.maxa+rr.lazy)*2;
		//cout<<i<<" "<<wtf<<" "<<(rr.maxa+rr.lazy)<<"\n";
		seg2.upd2(1,0,kaf-1,stf[i].first,stf[i].first,wtf);
	}
	long long lasta=0;
	for(int i=0;i<q;i++){
		long long we,e;
		cin>>e>>we;
		e+=lasta;
		we+=lasta;
		e%=n-1;
		we%=w;
		//cout<<e<<" "<<we<<" "<<alled[e].w<<"\n";
		//cout<<e<<" "<<we<<"\n";
		int v=alled[e].getad(alled[e].par);
		//cout<<"upd "<<v<<"\n";
		seg.upd(1,0,kaf-1,stf[v].first,stf[v].second,-alled[e].w);;
		seg2.upd(1,0,kaf-1,stf[v].first,stf[v].second,+alled[e].w);
		alled[e].w=we;
		seg.upd(1,0,kaf-1,stf[v].first,stf[v].second,alled[e].w);
		seg2.upd(1,0,kaf-1,stf[v].first,stf[v].second,-alled[e].w);
		update(v);
		v=vala[seg.seg[1].w];
		node nn=seg.pors(1,0,kaf-1,stf[v].first,stf[v].second);
		lasta=pors(v,nn.maxa+nn.lazy);
		//cout<<v<<" "<<nn.maxa+nn.lazy<<"\n";
		cout<<lasta<<"\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