제출 #1305447

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

diameter

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC optimize("inline") 
//~ #pragma GCC target("avx2","sse4.2","popcnt")
#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];
unordered_map<int,int>in[MAXN],out[MAXN],rc[MAXN],sig[MAXN];
multiset<int>ms[MAXN];
multiset<int>m;
int n,tim,sz[MAXN],ew[MAXN],z[MAXN],anc[MAXN],tam[MAXN],bst[MAXN],cen[MAXN];
bool rmv[MAXN];
static inline void apply(int root,int v,int x){
	st[root][v]+=x;
	lz[root][v]+=x;
}
static inline 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;
}
static inline 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]);
	}
}
static inline 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));
	}
}
static inline 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[root][i]=v;
		dfs(v,root,top,c,u);
	}
	out[root][u]=tim-1;
}
static inline 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];
}
static inline 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;
}
static inline int centroidDecomposition(int u=1,int p=-1){
	int treeSize=getSizes(u);
	int centroid=getCentroid(u,treeSize); 
	//~ cout<<"======================="<<endl;
	//~ cout<<centroid<<endl;
	rmv[centroid]=true;
	vector<int>c;
	c.reserve(treeSize);
	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);
	z[centroid]=0;
	fore(i,0,SZ(c)){
		//~ cout<<c[i]<<" "<<z[c[i]]<<endl;
		upd(centroid,in[centroid][c[i]],out[centroid][c[i]],z[c[i]],0,nn-1);
	}
	//~ cout<<endl;
	for(auto&[v,i]:adj[centroid]){
		if(rmv[v])continue;
		//~ cout<<v<<" "<<que(centroid,in[centroid][v],out[centroid][v],0,nn-1)<<endl;
		ms[centroid].insert(que(centroid,in[centroid][v],out[centroid][v],0,nn-1));
	}
	if(p!=-1)anc[centroid]=p;
	int ans=0;
	if(SZ(ms[centroid])==1)ans=*ms[centroid].begin();
	else if(SZ(ms[centroid])>1)ans=*prev(ms[centroid].end())+*prev(prev(ms[centroid].end()));
	bst[centroid]=ans;
	m.insert(bst[centroid]);
	for(auto&[v,i]:adj[centroid]){
		if(rmv[v])continue;
		cen[i]=centroidDecomposition(v,centroid);
	}
	return centroid;
}
static inline 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)));
	upd(centroid,in[centroid][sig[centroid][i]],out[centroid][sig[centroid][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));
	int ans=0;
	if(SZ(ms[centroid])==1)ans=*ms[centroid].begin();
	else ans=*prev(ms[centroid].end())+*prev(prev(ms[centroid].end()));
	m.erase(m.find(bst[centroid]));
	bst[centroid]=ans;
	m.insert(bst[centroid]);
	updCentroidTree(anc[centroid],x,i);
}
int32_t main(){
    int q;
    ll w;
    scanf("%lli%lli%lli",&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();
    //~ fore(i,1,n+1)cout<<bst[i]<<" ";
    //~ cout<<endl;
    //~ if(SZ(ms[5])==1)cout<<*ms[5].begin()<<endl;
	//~ else cout<<*prev(ms[5].end())<<"+"<<*prev(prev(ms[5].end()))<<endl;
    //~ cout<<*prev(m.end())<<endl;
    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[cen[d]],diff,d);
		printf("%lli\n",*prev(m.end()));
		last=*prev(m.end());
    }
}

컴파일 시 표준 에러 (stderr) 메시지

diameter.cpp: In function 'int32_t main()':
diameter.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |     scanf("%lli%lli%lli",&n,&q,&w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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