제출 #1305310

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305310		vtnoo	Dynamic Diameter (CEOI19_diameter)	C++20	0 / 100	1160 ms	315968 KiB

diameter

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
#define int long long
const int MAXN=1e5+9, INF=1e18;
vector<pair<int,int>>adj[MAXN];
vector<int>st[MAXN],lz[MAXN];
map<int,int>in[MAXN],out[MAXN],rc[MAXN];
multiset<int>ms[MAXN];
multiset<int>m;
int n,tim,sz[MAXN],ew[MAXN],z[MAXN],anc[MAXN],sig[MAXN],tam[MAXN];
bool rmv[MAXN];
void apply(int root,int v,int x){
	st[root][v]+=x;
	lz[root][v]+=x;
}
void push(int root,int v){
	apply(root,v*2,lz[root][v]);
	apply(root,v*2+1,lz[root][v]);
	lz[root][v]=0;
}
void upd(int root,int ts,int te,int x,int s,int e,int v=1){
	if(e<ts||te<s)return;
	if(ts<=s&&e<=te){
		apply(root,v,x);
		return;
	}else{
		push(root,v);
		int m=(s+e)/2;
		upd(root,ts,te,x,s,m,v*2);
		upd(root,ts,te,x,m+1,e,v*2+1);
		st[root][v]=max(st[root][v*2],st[root][v*2+1]);
	}
}
int que(int root,int ts,int te,int s,int e,int v=1){
	if(e<ts||te<s)return -INF;
	if(ts<=s&&e<=te){
		return st[root][v];
	}else{
		push(root,v);
		int m=(s+e)/2;
		return max(que(root,ts,te,s,m,v*2),que(root,ts,te,m+1,e,v*2+1));
	}
}
void dfs(int u,int root,int top,vector<int>&c,int p=-1){
	in[root][u]=tim++;
	c.pb(u);
	for(auto[v,i]:adj[u]){
		if(rmv[v]||v==p)continue;
		top=(u==root?v:top);
		z[v]=ew[i];
		rc[root][i]=top;
		sig[i]=v;
		dfs(v,root,top,c,u);
	}
	out[root][u]=tim-1;
}
int getSizes(int u,int p=-1){
	sz[u]=1;
	for(auto[v,i]:adj[u]){
		if(rmv[v]||v==p)continue;
		sz[u]+=getSizes(v,u);
	}
	return sz[u];
}
int getCentroid(int u,int treeSize,int p=-1){
	for(auto[v,i]:adj[u]){
		if(rmv[v]||v==p)continue;
		if(sz[v]>treeSize/2)return getCentroid(v,treeSize,u);
	}
	return u;
}
void centroidDecomposition(int u=1,int p=-1){
	int treeSize=getSizes(u);
	int centroid=getCentroid(u,treeSize); 
	rmv[centroid]=true;
	vector<int>c;
	tim=0;
	dfs(centroid,centroid,-1,c);
	int nn=1;
	while(nn<treeSize)nn*=2;
	tam[centroid]=nn;
	st[centroid].resize(nn*2,0);
	lz[centroid].resize(nn*2,0);
	fore(i,0,SZ(c)){
		upd(centroid,in[centroid][c[i]],out[centroid][c[i]],z[c[i]],0,nn-1);
	}
	for(auto[v,i]:adj[centroid]){
		ms[centroid].insert(que(centroid,in[centroid][v],out[centroid][v],0,nn-1));
	}
	if(p!=-1)anc[centroid]=p;
	for(auto v:ms[centroid]){
		m.insert(v);
	}
	for(auto[v,i]:adj[centroid]){
		if(rmv[v])continue;
		centroidDecomposition(v,centroid);
	}
}
void updCentroidTree(int centroid,int x,int i){
	if(centroid==0)return;
	ms[centroid].erase(ms[centroid].find(que(centroid,in[centroid][rc[centroid][i]],out[centroid][rc[centroid][i]],0,tam[centroid]-1)));
	m.erase(m.find(que(centroid,in[centroid][rc[centroid][i]],out[centroid][rc[centroid][i]],0,tam[centroid]-1)));
	upd(centroid,in[centroid][sig[i]],out[centroid][sig[i]],x,0,tam[centroid]-1);
	ms[centroid].insert(que(centroid,in[centroid][rc[centroid][i]],out[centroid][rc[centroid][i]],0,tam[centroid]-1));
	m.insert(que(centroid,in[centroid][rc[centroid][i]],out[centroid][rc[centroid][i]],0,tam[centroid]-1));
	updCentroidTree(anc[centroid],x,i);
}
signed main(){FIN;
    int q;
    ll w;
    cin>>n>>q>>w;
    fore(i,0,n-1){
        int u,v;
        ll c;
        cin>>u>>v>>c;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
        ew[i]=c;
    }
    centroidDecomposition();
    ll last=0;
    while(q--){
        ll d_, e_;
        cin>>d_>>e_;
        ll d=(d_+last)%(n-1);
        ll e=(e_+last)%w;
        ll diff=e-ew[d];
        ew[d]=e;
		updCentroidTree(anc[sig[d]],diff,d);
		ll ans;
		if(SZ(m)==1)ans=*m.begin();
		else ans=*prev(m.end())+*prev(prev(m.end()));
		cout<<ans<<endl;
		last=ans;
    }
}

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