(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #579275

#TimeUsernameProblemLanguageResultExecution timeMemory
579275temporary_juggernautDynamic Diameter (CEOI19_diameter)C++14
100 / 100
4559 ms200784 KiB
#include<bits/stdc++.h> #define fr first #define sc second using namespace std; typedef long long ll; typedef long double ld; #define USING_ORDERED_SET 0 #if USING_ORDERED_SET #include<bits/extc++.h> using namespace __gnu_pbds; template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; #endif template<class T>void umax(T &a,T b){if(a<b)a=b;} template<class T>void umin(T &a,T b){if(b<a)a=b;} #ifdef juggernaut #define printl(args...) printf(args) #else #define printl(args...) 0 #endif int n,q; int timer[20]; int tin[100005][20]; int tout[100005][20]; ll w[100005]; multiset<ll>st[100005]; pair<int,int>edge[100005]; vector<pair<int,int>>g[100005]; bool vis[100005]; int sz[100005]; int par[100005]; int depth[100005]; int prepar[100005][20]; struct MultiSegmentTree{ vector<ll>tree; vector<ll>lazy; MultiSegmentTree(){ } MultiSegmentTree(int n){ tree.assign(n<<2|3,0ll); lazy.assign(n<<2|3,0ll); } void push(int v,bool bit){ if(bit){ lazy[v<<1]+=lazy[v]; lazy[v<<1|1]+=lazy[v]; } tree[v]+=lazy[v]; lazy[v]=0; } ll get(int ql,int qr,int v,int l,int r){ if(qr<l||r<ql)return 0ll; push(v,l^r); if(ql<=l&&r<=qr)return tree[v]; int mid=(l+r)>>1; return max(get(ql,qr,v<<1,l,mid),get(ql,qr,v<<1|1,mid+1,r)); } void update(int ql,int qr,ll val,int v,int l,int r){ push(v,l^r); if(qr<l||r<ql)return; if(ql<=l&&r<=qr){ lazy[v]+=val; push(v,l^r); return; } int mid=(l+r)>>1; update(ql,qr,val,v<<1,l,mid); update(ql,qr,val,v<<1|1,mid+1,r); tree[v]=max(tree[v<<1],tree[v<<1|1]); } }; MultiSegmentTree tree[20],alls; void build_sz(int v,int p){ sz[v]=1; for(auto &to:g[v])if((to.fr^p)&&(!vis[to.fr])){ build_sz(to.fr,v); sz[v]+=sz[to.fr]; } } int centroid(int v,int p,int sz){ bool can; while(true){ can=true; for(auto &to:g[v])if((to.fr^p)&&(!vis[to.fr])){ if(::sz[to.fr]>sz){ can=false; p=v; v=to.fr; break; } } if(can)return v; } } void build_tin(int v,int p,int &depth,int &kylych){ tin[v][depth]=++timer[depth]; prepar[v][depth]=kylych; for(auto &to:g[v])if((to.fr^p)&&(!vis[to.fr]))build_tin(to.fr,v,depth,kylych); tout[v][depth]=timer[depth]; } ll cash; unordered_map<int,ll>csh[100005]; ll scs[100005]; void go(int v,int p,int &depth,ll kylych){ tree[depth].update(tin[v][depth],tin[v][depth],kylych,1,1,n); umax(cash,kylych); for(auto &to:g[v])if((to.fr^p)&&(!vis[to.fr]))go(to.fr,v,depth,kylych+w[to.sc]); } void build(int v,int p,int dep){ build_sz(v,0); v=centroid(v,0,sz[v]>>1); tin[v][dep]=++timer[dep]; for(auto &to:g[v])if((to.fr^p)&&(!vis[to.fr])){ build_tin(to.fr,v,dep,to.fr); } tout[v][dep]=timer[dep]; for(auto &to:g[v])if((to.fr^p)&&(!vis[to.fr])){ cash=0; go(to.fr,v,dep,w[to.sc]); st[v].insert(cash); csh[v][to.fr]=cash; } //CALC ALLS if(!st[v].empty()){ ll ans=0; auto it=st[v].rbegin(); ans+=*it; if((int)st[v].size()!=1){ it++; ans+=*it; } scs[v]=ans; alls.update(v,v,ans,1,1,n); } //END par[v]=p; depth[v]=dep; vis[v]=true; for(auto &to:g[v])if(!vis[to.fr])build(to.fr,v,dep+1); } ll ans; int cand_x,cand_y; void edit(int v,ll val){ int x=cand_x; int y=cand_y; if(tin[x][depth[v]]<tin[y][depth[v]])swap(x,y); int child=prepar[x][depth[v]]; st[v].erase(st[v].find(csh[v][child])); tree[depth[v]].update(tin[x][depth[v]],tout[x][depth[v]],val,1,1,n); csh[v][child]=tree[depth[v]].get(tin[child][depth[v]],tout[child][depth[v]],1,1,n); st[v].insert(csh[v][child]); ll ans=0; auto it=st[v].rbegin(); ans+=*it; if((int)st[v].size()!=1){ it++; ans+=*it; } alls.update(v,v,ans-scs[v],1,1,n); scs[v]=ans; } int main(){ scanf("%d%d%lld",&n,&q,&w[0]); for(int i=0;i<20;i++)tree[i]=MultiSegmentTree(n); alls=MultiSegmentTree(n); for(int i=1;i^n;i++){ scanf("%d%d%lld",&edge[i].fr,&edge[i].sc,&w[i]); g[edge[i].fr].emplace_back(edge[i].sc,i); g[edge[i].sc].emplace_back(edge[i].fr,i); } build(1,0,0); for(int i=1;i^n;i++)if(depth[edge[i].fr]>depth[edge[i].sc])swap(edge[i].fr,edge[i].sc); while(q--){ ll x; ll y; scanf("%lld%lld",&x,&y); x=((x+ans)%(n-1))+1; y=(y+ans)%w[0]; ll pivot=y-w[x]; w[x]=y; cand_x=edge[x].fr; cand_y=edge[x].sc; x=edge[x].fr; while(x){ edit(x,pivot); x=par[x]; } ans=alls.get(1,n,1,1,n); printl("______________________"); printf("%lld\n",ans); } }

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:18:29: warning: statement has no effect [-Wunused-value]
   18 |     #define printl(args...) 0
      |                             ^
diameter.cpp:188:3: note: in expansion of macro 'printl'
  188 |   printl("______________________");
      |   ^~~~~~
diameter.cpp:162:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |  scanf("%d%d%lld",&n,&q,&w[0]);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:166:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |   scanf("%d%d%lld",&edge[i].fr,&edge[i].sc,&w[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:175:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
#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...