제출 #618878

#제출 시각아이디문제언어결과실행 시간메모리
618878senthetaDynamic Diameter (CEOI19_diameter)C++17
24 / 100
5056 ms10248 KiB
#include<algorithm> #include<iostream> #include<cassert> #include<vector> #include<string> #include<array> #include<stack> #include<queue> #include<map> #include<set> using namespace std; #define V vector #define Int long long #define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++) #define nl '\n' #define dbg(x) cout << "?" << #x << " : " << x << endl; #define all(x) (x).begin(), (x).end() #define int long long #define pii pair<int,int> const int N = 1e5+5; int n, q, wlim; V<array<int,3>> edges; V<pair<int,int>> queries; struct Sub1{ V<int> adj[N]; int mxdist = 0, mxnode = -1; void dfs(int x,int par=-1,int dist=0){ if(dist >= mxdist){ mxdist = dist; mxnode = x; } for(int id : adj[x]){ int y = edges[id][0]^edges[id][1]^x; int w = edges[id][2]; if(y==par) continue; dfs(y,x, dist+w); } } void run(){ rep(i,0,n-1){ auto[u,v,w] = edges[i]; adj[u].push_back(i); adj[v].push_back(i); } int last = 0; for(auto[i,w] : queries){ i = (i+last)%(n-1); w = (w+last)%wlim; edges[i][2] = w; mxdist = 0; dfs(1); dfs(mxnode); cout << mxdist << nl; last = mxdist; } } }; struct Sub3{ int arr[N]; multiset<int> s; void run(){ rep(i,0,n-1){ auto[u,v,w] = edges[i]; u = u^v^1; arr[u] = w; s.insert(w); } int last = 0; for(auto[i,w] : queries){ i = (i+last)%(n-1); w = (w+last)%wlim; s.erase(s.find(arr[i])); arr[i] = w; s.insert(w); int ans = *prev(s.end()); if(s.size() >= 2){ ans += *prev(prev(s.end())); } cout << ans << nl; last = ans; } } }; signed main(){ cin >> n >> q >> wlim; rep(i,0,n-1){ int u, v, w; cin >> u >> v >> w; edges.push_back({u,v,w}); } rep(i,0,q){ int idx, w; cin >> idx >> w; queries.push_back({idx,w}); } bool sub3 = 1; rep(i,0,n-1){ auto[u,v,w] = edges[i]; sub3 &= (u==1 || v==1); } if(sub3){ Sub3 sub; sub.run(); return 0; } Sub1 sub; sub.run(); return 0; }
#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...