Submission #623449

#TimeUsernameProblemLanguageResultExecution timeMemory
623449pliamDynamic Diameter (CEOI19_diameter)C++14
49 / 100
4170 ms183068 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 100005 typedef long long ll; typedef pair<ll,int> pli; typedef pair<pli,pli> ppli; #define INF 1000005 int Q; ll N,W; vector<int> adj[MAXN]; vector<pair<int,int>> edges; map<pair<int,int>,ll> w;//each edge is stored with two elements (order of the pair) ll last; //centroid decomposition vector<int> ch[MAXN]; int par[MAXN],sz[MAXN],r[MAXN]; map<pair<int,int>,vector<pair<int,int>>> edge_info;//edge->(centroid,order of child), for the ancestors (O(logN)) worst-case vector<pair<int,int>> leaf_range[MAXN];//range of leaves for each centroid and for each vertex(vertices are in dfs order) vector<ll> st[MAXN];//max segment tree for each centroid vector<ll> lazy[MAXN]; vector<ll> chp_sub[MAXN];//dfs-order->head order int num_leaf[MAXN];//for each centroid number of leaves int curcen,dfs_order,leaf_order; ll leaf_dist[MAXN];//temporary for build centroid st set<pli,greater<pli>> mxpaths[MAXN]; set<pli,greater<pli>> diams;//holds for each centroid the diameter vector<ll> order_ch[MAXN]; //segment tree void build(int c,int v,int start,int end){ if(start==end){ st[c][v]=leaf_dist[start]; lazy[c][v]=0; return; } int mid=(start+end)/2; build(c,2*v,start,mid); build(c,2*v+1,mid+1,end); st[c][v]=max(st[c][2*v],st[c][2*v+1]); } void update(int c,int from,int to,ll val,int v,int start,int end){ if(start==from&&end==to){ st[c][v]+=val; lazy[c][v]+=val; return; } int mid=(start+end)/2; //propagate if(lazy[c][v]){ update(c,start,mid,lazy[c][v],2*v,start,mid); update(c,mid+1,end,lazy[c][v],2*v+1,mid+1,end); lazy[c][v]=0; } if(to<=mid){ update(c,from,to,val,2*v,start,mid); }else if(from>mid){ update(c,from,to,val,2*v+1,mid+1,end); }else{ update(c,from,mid,val,2*v,start,mid); update(c,mid+1,to,val,2*v+1,mid+1,end); } st[c][v]=max(st[c][2*v],st[c][2*v+1]); } ll query(int c,int from,int to,int v,int start,int end){//for full query: st[c][1] if(start==from&&end==to){ return st[c][v]; } int mid=(start+end)/2; //propagate if(lazy[c][v]){ update(c,start,mid,lazy[c][v],2*v,start,mid); update(c,mid+1,end,lazy[c][v],2*v+1,mid+1,end); lazy[c][v]=0; } if(to<=mid){ return query(c,from,to,2*v,start,mid); }else if(from>mid){ return query(c,from,to,2*v+1,mid+1,end); }else{ return max(query(c,from,mid,2*v,start,mid),query(c,mid+1,to,2*v+1,mid+1,end)); } } void dfs_sz(int curr,int p){ sz[curr]=1; for(int to:adj[curr]){ if(to==p||r[to]) continue; dfs_sz(to,curr); sz[curr]+=sz[to]; } } int centroid(int curr,int p,int n){ for(int to:adj[curr]){ if(to==p||r[to]) continue; if(2*sz[to]>n) return centroid(to,curr,n); } return curr; } int dfs_cen(int curr,int p,int d,int s,int ch_p){//returns dfs order int ord=dfs_order++; chp_sub[curcen].push_back(ch_p?ord:s); leaf_range[curcen].push_back({INF,0});//placeholder if(p!=-1){ edge_info[{curr,p}].push_back({curcen,ord}); edge_info[{p,curr}].push_back({curcen,ord}); } int leaf=1; for(int to:adj[curr]){ if(to==p||r[to]) continue; leaf=0; int ordch=dfs_cen(to,curr,d+w[{curr,to}],ch_p?ord:s,p==-1); if(p==-1) order_ch[curcen].push_back(ordch); leaf_range[curcen][ord].first=min(leaf_range[curcen][ord].first,leaf_range[curcen][ordch].first); leaf_range[curcen][ord].second=max(leaf_range[curcen][ord].second,leaf_range[curcen][ordch].second); } if(leaf){ leaf_order++; leaf_dist[leaf_order]=d; leaf_range[curcen][ord]={leaf_order,leaf_order}; } return ord; } ll diam(int cen,int ch){ return query(cen,leaf_range[cen][ch].first,leaf_range[cen][ch].second,1,1,num_leaf[cen]); } ll tdiam(int cen){ ll d=0; if(!mxpaths[cen].empty()){ auto it=mxpaths[cen].begin(); d+=it->first; if(mxpaths[cen].size()>=2){ it++; d+=it->first; } } return d; } //returns centroid int centroid_decomp(int curr,int p=-1){ dfs_sz(curr,-1); int cen=centroid(curr,-1,sz[curr]); curcen=cen; //now prepare stuff this centroid dfs_order=0; leaf_order=0; dfs_cen(cen,-1,0,0,1); st[cen]=vector<ll>(4*leaf_order,0); lazy[cen]=vector<ll>(4*leaf_order,0); num_leaf[cen]=leaf_order; build(cen,1,1,num_leaf[cen]); for(int to:order_ch[cen]){ mxpaths[cen].insert({diam(cen,to),to}); } diams.insert({tdiam(cen),cen}); //-- r[cen]=1; par[cen]=p; for(int to:adj[cen]){ if(r[to]) continue; int c_to=centroid_decomp(to,cen); ch[cen].push_back(c_to); } return cen; } ll query_cen(int a,int b,ll we){ ll diff=we-w[{a,b}]; w[{a,b}]=w[{b,a}]=we; auto changes=edge_info[{a,b}]; for(auto p:changes){ int cen,ord; tie(cen,ord)=p; diams.erase({tdiam(cen),cen}); mxpaths[cen].erase({diam(cen,chp_sub[cen][ord]),chp_sub[cen][ord]}); update(cen,leaf_range[cen][ord].first,leaf_range[cen][ord].second,diff,1,1,num_leaf[cen]); mxpaths[cen].insert({diam(cen,chp_sub[cen][ord]),chp_sub[cen][ord]}); diams.insert({tdiam(cen),cen}); } return diams.begin()->first; } void initialize(){ centroid_decomp(1); } int main(){ //freopen("ddiameter.in","r",stdin); scanf("%d%d%lld",&N,&Q,&W); for(int i=0;i<N-1;i++){ int a,b; ll c; scanf("%d%d%lld",&a,&b,&c); edges.push_back({a,b}); adj[a].push_back(b); adj[b].push_back(a); w[{a,b}]=c; w[{b,a}]=c; } initialize(); while(Q--){ ll d;ll e; scanf("%lld%lld",&d,&e); d=(d+last)%(N-1); e=(e+last)%W; last=query_cen(edges[d].first,edges[d].second,e); printf("%lld\n",last); } }

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:198:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
  198 |     scanf("%d%d%lld",&N,&Q,&W);
      |            ~^        ~~
      |             |        |
      |             int*     ll* {aka long long int*}
      |            %lld
diameter.cpp:198:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |     scanf("%d%d%lld",&N,&Q,&W);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp:202:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |         scanf("%d%d%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp:212:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |         scanf("%lld%lld",&d,&e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
#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...