제출 #540915

#제출 시각아이디문제언어결과실행 시간메모리
540915jamezzzDynamic Diameter (CEOI19_diameter)C++17
49 / 100
5088 ms238504 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #define dbg(...) printf(__VA_ARGS__); #define getchar_unlocked getchar #else #define dbg(...) #endif #define sf scanf #define pf printf #define fi first #define se second #define pb push_back #define sz(x) (int)x.size() #define mnto(x,y) x=min(x,(__typeof__(x))y) #define mxto(x,y) x=max(x,(__typeof__(x))y) #define INF 1023456789 #define LINF 1023456789123456789 #define all(x) x.begin(), x.end() #define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin()); typedef long long ll; typedef long double ld; typedef pair<int,int> ii; typedef pair<ll,int> li; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<pll> vll; mt19937 rng(time(0)); #define mod 1000000007 inline int add(int a,int b){ int r=a+b; while(r>=mod)r-=mod; while(r<0)r+=mod; return r; } inline int mult(int a,int b){ return (int)(((ll)(a*b))%mod); } inline int rd(){ int x=0; char ch=getchar_unlocked(); while(!(ch&16))ch=getchar();//keep reading while current character is whitespace while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered x=(x<<3)+(x<<1)+(ch&15); ch=getchar_unlocked(); } return x; } #define maxn 100005 struct edge{ int u,v;ll w; vector<int> comp; vector<ii> range; }; struct node{ int s,e,m; li v;ll lz; node *l,*r; node(int _s,int _e){ s=_s;e=_e;m=(s+e)/2;lz=0;v={0,s}; if(s!=e)l=new node(s,m),r=new node(m+1,e); } void ppo(){ v.fi+=lz; if(s!=e)l->lz+=lz,r->lz+=lz; lz=0; } void up(int x,int y,ll nv){ if(s==x&&e==y){lz+=nv;return;} if(y<=m)l->up(x,y,nv); else if(x>m)r->up(x,y,nv); else l->up(x,m,nv),r->up(m+1,y,nv); l->ppo();r->ppo(); v=max(l->v,r->v); } void print(){ pf("%d %d %lld %lld\n",s,e,v.fi,lz); if(s!=e)l->print(),r->print(); } }; struct tree{ int s,e; node *root; vector<int> block; vector<ii> ranges; tree(int _s,int _e){ s=_s;e=_e; root=new node(s,e); block.resize(e-s+1); } void up(int x,int y,ll nv){ root->up(x,y,nv); } ll qry(){ root->ppo(); ll ans=root->v.fi; int i=block[root->v.se]; root->up(ranges[i].fi,ranges[i].se,-LINF); if(root->v.fi>=0)ans+=root->v.fi; up(ranges[i].fi,ranges[i].se,LINF); return ans; } }*root[maxn]; int n,q,sub[maxn];ll w; bool mark[maxn]; vii AL[maxn]; vector<edge> edges; void find_sz(int u,int p){ sub[u]=1; for(auto[v,i]:AL[u]){ if(mark[v]||v==p)continue; find_sz(v,u); sub[u]+=sub[v]; } } int cnt; vii ranges; ii dfs(int u,int p,int c){ ii range={cnt,cnt};++cnt; for(auto[v,i]:AL[u]){ if(mark[v]||v==p)continue; ii res=dfs(v,u,c); edges[i].comp.pb(c); edges[i].range.pb(res); mxto(range.se,res.se); if(p==-1)ranges.pb(res); } return range; } void decomp(int u){ dbg("decomp: %d\n",u); dbg("find centroid\n"); find_sz(u,-1); int c=u; while(true){ bool val=true; for(auto[v,i]:AL[c]){ if(!mark[v]&&sub[v]<sub[c]&&sub[v]>sub[u]/2){ c=v;val=false;break; } } if(val)break; } dbg("centroid: %d\n",c); cnt=0; ranges.clear(); dbg("dfs\n"); dfs(c,-1,c); dbg("create node\n"); root[c]=new tree(0,cnt-1); dbg("%d\n",sz(ranges)); for(int i=0;i<sz(ranges);++i){ dbg("add range: %d %d\n",ranges[i].fi,ranges[i].se); root[c]->ranges.pb(ranges[i]); for(int j=ranges[i].fi;j<=ranges[i].se;++j){ root[c]->block[j]=i; } } mark[c]=true; for(auto[v,i]:AL[c]){ if(!mark[v])decomp(v); } } int main(){ sf("%d%d%lld",&n,&q,&w); for(int i=0;i<n-1;++i){ int a,b;ll c; sf("%d%d%lld",&a,&b,&c); AL[a].pb({b,i}); AL[b].pb({a,i}); edges.pb({a,b,c,{},{}}); } decomp(1); for(auto &e:edges){ dbg("edge: %d %d %lld\n",e.u,e.v,e.w); for(int i=0;i<sz(e.comp);++i){ ii rng=e.range[i]; dbg("comp: %d %d %d\n",e.comp[i],rng.fi,rng.se); root[e.comp[i]]->up(rng.fi,rng.se,e.w); } } set<li> s; for(int i=1;i<=n;++i){ if(root[i]->s==root[i]->e)continue; dbg("%d: %lld\n",i,root[i]->qry()); s.insert({root[i]->qry(),i}); } ll ans=0; for(int i=0;i<q;++i){ int idx;ll nw; sf("%d%lld",&idx,&nw); idx=(idx+ans)%(n-1); nw=(nw+ans)%w; edge &e=edges[idx]; ll ow=e.w; e.w=nw; //dbg("upd: %d %lld\n",idx,nw); for(int i=0;i<sz(e.comp);++i){ ii rng=e.range[i]; int c=e.comp[i]; ll old=root[c]->qry(); root[c]->up(rng.fi,rng.se,nw-ow); ll upd=root[c]->qry(); s.erase(s.find({old,c})); s.insert({upd,c}); } ans=(*--s.end()).fi; pf("%lld\n",ans); } }

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

diameter.cpp: In function 'int main()':
diameter.cpp:192:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |  sf("%d%d%lld",&n,&q,&w);
      |    ^
diameter.cpp:195:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |   sf("%d%d%lld",&a,&b,&c);
      |     ^
diameter.cpp:222:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  222 |   sf("%d%lld",&idx,&nw);
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...