제출 #619054

#제출 시각아이디문제언어결과실행 시간메모리
619054HappyPacManDynamic Diameter (CEOI19_diameter)C++14
31 / 100
5063 ms426316 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") using namespace std; using ll = long long; const int maxn = 1e5 + 3; vector<pair<int,int> > adj[maxn],edges; vector<int> partOf[maxn]; vector<ll> seg[maxn],lazy[maxn]; bool isCent[maxn]; int subSz[maxn],centRoot,timer[maxn]; map<int,int> tin[maxn],tout[maxn],edgeRoot[maxn]; set<pair<ll,int> > bestEdge[maxn],result; ll cost[maxn]; void dfsSz(int u,int p){ subSz[u] = 1; for(auto [v,w] : adj[u]){ if(v != p && !isCent[v]){ dfsSz(v,u); subSz[u] += subSz[v]; } } } int fnCent(int u,int p,int s){ for(auto [v,w] : adj[u]){ if(v != p && !isCent[v] && subSz[v] > s/2){ return fnCent(v,u,s); } } return u; } void dfsTour(int c,int u,int p){ for(auto [v,w] : adj[u]){ if(v != p && !isCent[v]){ partOf[w].emplace_back(c); tin[c][w] = timer[c]++; dfsTour(c,v,u); tout[c][w] = timer[c]++; } } } void dfsEdgeRoot(int c,int d,int u,int p){ for(auto [v,w] : adj[u]){ if(v != p && !isCent[v]){ edgeRoot[c][w] = d; dfsEdgeRoot(c,d,v,u); } } } void dfsCent(int u,int p){ dfsSz(u,p); int cent = fnCent(u,u,subSz[u]); isCent[cent] = true; if(p != -1){ centRoot = cent; } dfsTour(cent,cent,cent); for(auto [v,w] : adj[cent]){ if(!isCent[v]){ bestEdge[cent].emplace(0,w); edgeRoot[cent][w] = w; dfsEdgeRoot(cent,w,v,cent); } } seg[cent].resize(4*timer[cent]); lazy[cent].resize(4*timer[cent]); for(auto [v,w] : adj[cent]){ if(!isCent[v]){ dfsCent(v,cent); } } } // Segment Tree + Lazy Propagation void push(int c,int i){ lazy[c][i<<1] += lazy[c][i]; seg[c][i<<1] += lazy[c][i]; lazy[c][i<<1|1] += lazy[c][i]; seg[c][i<<1|1] += lazy[c][i]; lazy[c][i] = 0; } void upd(int c,int i,int l,int r,int ul,int ur,ll v){ if(ul <= l && r <= ur){ seg[c][i] += v; lazy[c][i] += v; }else if(ul > r || ur < l){ return; }else{ int m = (l+r)/2; push(c,i); upd(c,i<<1,l,m,ul,ur,v); upd(c,i<<1|1,m+1,r,ul,ur,v); seg[c][i] = max(seg[c][i<<1],seg[c][i<<1|1]); } } ll qry(int c,int i,int l,int r,int ql,int qr){ if(ql <= l && r <= qr){ return seg[c][i]; }else if(ql > r || qr < l){ return 0; }else{ int m = (l+r)/2; push(c,i); return max(qry(c,i<<1,l,m,ql,qr),qry(c,i<<1|1,m+1,r,ql,qr)); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,q; ll w; cin >> n >> q >> w; for(int i=1;i<n;i++){ int u,v; ll w; cin >> u >> v >> w; u--; v--; adj[u].emplace_back(v,i); adj[v].emplace_back(u,i); edges.emplace_back(u,v); cost[i] = w; } dfsCent(0,-1); for(int i=1;i<n;i++){ for(int it : partOf[i]){ bestEdge[it].erase(bestEdge[it].find(make_pair(qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]),edgeRoot[it][i]))); upd(it,1,0,timer[it]-1,tin[it][i],timer[it]-1,cost[i]); upd(it,1,0,timer[it]-1,tout[it][i],timer[it]-1,-cost[i]); bestEdge[it].insert(make_pair(qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]),edgeRoot[it][i])); } } for(int i=0;i<n;i++){ if(bestEdge[i].size() > 1){ result.emplace((*prev(bestEdge[i].end())).first+(*prev(prev(bestEdge[i].end()))).first,i); }else if(bestEdge[i].size()){ result.emplace((*prev(bestEdge[i].end())).first,i); }else{ result.emplace(0,i); } } ll last = 0; while(q--){ int i; ll j; cin >> i >> j; i = (i+last)%(n-1)+1; j = (j+last)%w; ll df = j-cost[i]; for(int it : partOf[i]){ if(bestEdge[it].size() > 1){ result.erase(result.find(make_pair((*prev(bestEdge[it].end())).first+(*prev(prev(bestEdge[it].end()))).first,it))); }else if(bestEdge[it].size()){ result.erase(result.find(make_pair((*prev(bestEdge[it].end())).first,it))); }else{ result.erase(result.find(make_pair(0,it))); } bestEdge[it].erase(bestEdge[it].find(make_pair(qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]),edgeRoot[it][i]))); upd(it,1,0,timer[it]-1,tin[it][i],timer[it]-1,df); upd(it,1,0,timer[it]-1,tout[it][i],timer[it]-1,-df); bestEdge[it].insert(make_pair(qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]),edgeRoot[it][i])); if(bestEdge[it].size() > 1){ result.emplace((*prev(bestEdge[it].end())).first+(*prev(prev(bestEdge[it].end()))).first,it); }else if(bestEdge[it].size()){ result.emplace((*prev(bestEdge[it].end())).first,it); }else{ result.emplace(0,it); } } cost[i] = j; last = (*prev(result.end())).first; cout << (*prev(result.end())).first << "\n"; } }

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

diameter.cpp: In function 'void dfsSz(int, int)':
diameter.cpp:19:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'int fnCent(int, int, int)':
diameter.cpp:27:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'void dfsTour(int, int, int)':
diameter.cpp:35:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'void dfsEdgeRoot(int, int, int, int)':
diameter.cpp:45:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'void dfsCent(int, int)':
diameter.cpp:60:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |  for(auto [v,w] : adj[cent]){
      |           ^
diameter.cpp:69:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |  for(auto [v,w] : adj[cent]){
      |           ^
#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...