제출 #604197

#제출 시각아이디문제언어결과실행 시간메모리
604197enter_hedgehog_polyDynamic Diameter (CEOI19_diameter)C++11
49 / 100
5099 ms102100 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define N 100010 struct Edge { ll w; int a, b; Edge() {} Edge(ll w, int a, int b) : w(w), a(a), b(b) {} int other(int x) const { return x == a ? b: a; } }; vector<Edge*> graf[N]; Edge edges[N]; int centroid[N]; int cdepth[N]; int depth[18][N]; int droot[18][N]; int calc_size_and_number(int n, int f, int cd, int p, int d); int decompose(int n, int f, int d) ; multiset<ll, greater<ll>> centroid_subtree_depths[N]; void erase(multiset<ll, greater<ll>> &st, ll val) { auto it = st.find(val); if(it != st.end()) st.erase(it); } const int tree_size = 1 << 17; //#define TS (tree_size >> min((qt - 1), 5)) #define TS tree_size ll tree[18][2*tree_size]; ll lazy[18][2*tree_size]; int pre[18][N]; int post[18][N]; int ql, qr, qt; ll qv; ll add_tree(int n, int lms, int rms); ll get_max(int n, int lms, int rms); int main() { ll n, q, w; cin >> n >> q >> w; for(int i = 0; i < n - 1; i++) { scanf("%d%d%lld", &edges[i].a, &edges[i].b, &edges[i].w); graf[edges[i].a].push_back(edges + i); graf[edges[i].b].push_back(edges + i); } if(n == 2) { ll last = 0; while(q--) { int edge_id; ll new_weight; scanf("%d%lld", &edge_id, &new_weight); last = new_weight = (new_weight + last) % w; printf("%lld\n", new_weight); } return 0; } auto t1 = chrono::high_resolution_clock::now(); calc_size_and_number(1, 0, 0, 1, 1); int r = decompose(1, 0, 1); centroid[r] = 0; auto t2 = chrono::high_resolution_clock::now(); for(auto i = 0; i < n - 1; i++) { Edge e = edges[i]; qv = e.w; for(int j = 1; j <= 18; j++) { if(!depth[j][e.a] || !depth[j][e.b]) break; int x = depth[j][e.a] < depth[j][e.b] ? e.b : e.a; qt = j; ql = TS + pre[j][x]; qr = TS + post[j][x]; add_tree(1, TS, 2*TS - 1); } } multiset<ll, greater<ll>> result; auto t3 = chrono::high_resolution_clock::now(); for(auto v = 1; v <= n; v++) { for(auto i: graf[v]) { if(cdepth[i->other(v)] < cdepth[v]) continue; qt = cdepth[v]; ql = pre[cdepth[v]][i->other(v)] + TS; qr = post[cdepth[v]][i->other(v)] + TS; ll x = get_max(1, TS, 2*TS - 1); centroid_subtree_depths[v].insert(x); } if(centroid_subtree_depths[v].size() > 1) result.insert(*centroid_subtree_depths[v].begin() + *++centroid_subtree_depths[v].begin()); } auto t4 = chrono::high_resolution_clock::now(); /* cout << "Phse 1: " << (double)(t2 - t1).count() / 1000000.0F << "ms" << endl; cout << "Phse 2: " << (double)(t3 - t2).count() / 1000000.0F << "ms" << endl; cout << "Phse 3: " << (double)(t4 - t3).count() / 1000000.0F << "ms" << endl; */ //return 0; ll last = 0; int mxd = 0; while(q--) { int edge_id; ll new_weight; scanf("%d%lld", &edge_id, &new_weight); edge_id = (int)(((ll)edge_id + last) % (n - 1)); new_weight = (new_weight + last) % w; Edge &e = edges[edge_id]; qv = new_weight - e.w; int c = cdepth[e.a] < cdepth[e.b] ? e.a : e.b; int cnt = 0; while(c) { if(centroid_subtree_depths[c].size() > 1) erase(result,*centroid_subtree_depths[c].begin() + *++centroid_subtree_depths[c].begin()); int d = cdepth[c]; int v = depth[d][e.a] < depth[d][e.b] ? e.b : e.a; qt = d; ql = pre[d][droot[d][v]] + TS; qr = post[d][droot[d][v]] + TS; ll x = get_max(1, TS, 2*TS - 1); erase(centroid_subtree_depths[c], x); ql = pre[d][v] + TS; qr = post[d][v] + TS; qv = new_weight - e.w; add_tree(1, TS, 2*TS - 1); ql = pre[d][droot[d][v]] + TS; qr = post[d][droot[d][v]] + TS; centroid_subtree_depths[c].insert(get_max(1, TS, 2*TS - 1)); if(centroid_subtree_depths[c].size() > 1) result.insert(*centroid_subtree_depths[c].begin() + *++centroid_subtree_depths[c].begin()); c = centroid[c]; cnt++; } e.w = new_weight; last = *result.begin(); //cout << cnt << endl; //mxd = max(mxd, cnt); printf("%lld\n", last); } //cout << mxd << endl; return 0; } void push_lazy(int t, int n) { tree[t][n] += lazy[t][n]; if(n < TS) { lazy[t][2 * n] += lazy[t][n]; lazy[t][2 * n + 1] += lazy[t][n]; } lazy[t][n] = 0; } ll add_tree(int n, int lms, int rms) { push_lazy(qt, n); if(ql <= lms && rms <= qr) { lazy[qt][n] += qv; push_lazy(qt, n); } else if(lms <= qr && ql <= rms) { int m = (lms + rms) >> 1; tree[qt][n] = max(add_tree(2*n, lms, m), add_tree(2*n + 1, m + 1, rms)); } return tree[qt][n]; } ll get_max(int n, int lms, int rms) { push_lazy(qt, n); if(ql <= lms && rms <= qr) return tree[qt][n]; else if(lms <= qr && ql <= rms) { int m = (lms + rms) >> 1; return max(get_max(2*n, lms, m), get_max(2*n + 1, m+ 1, rms)); } return 0; } int sub_tree_size[N]; int last_num[20]; int calc_size_and_number(int n, int f, int cd, int p, int d) { sub_tree_size[n] = 0; post[cd][n] = pre[cd][n] = p; depth[cd][n] = d; for(auto i: graf[n]) { if(i->other(n) == f || centroid[i->other(n)]) continue; p = calc_size_and_number(i->other(n), n, cd, p + 1, d + 1); sub_tree_size[n] += sub_tree_size[i->other(n)] + 1; } return post[cd][n] = p; } int find_centroid(int n, int root, int size, int f) { for (auto i: graf[n]) { if (i->other(n) == f || centroid[i->other(n)]) continue; if (sub_tree_size[i->other(n)] >= size / 2) return find_centroid(i->other(n), root, size, n); } return n; } void mark_droot(int n, int f, int cd, int r) { droot[cd][n] = r; for(auto i: graf[n]) { if(i->other(n) == f || centroid[i->other(n)]) continue; mark_droot(i->other(n), n, cd, r); } } int decompose(int n, int f, int d) { int r = find_centroid(n, f, sub_tree_size[n] + 1, 0); centroid[r] = f ? f: r; cdepth[r] = d; last_num[d] = calc_size_and_number(r, 0, d, ++last_num[d], 1); for(auto i: graf[r]) { if(centroid[i->other(r)]) continue; mark_droot(i->other(r), r, d, i->other(r)); decompose(i->other(r), r, d + 1); } return r; }

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

diameter.cpp: In function 'int main()':
diameter.cpp:74:7: warning: variable 't1' set but not used [-Wunused-but-set-variable]
   74 |  auto t1 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:81:7: warning: variable 't2' set but not used [-Wunused-but-set-variable]
   81 |  auto t2 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:99:7: warning: variable 't3' set but not used [-Wunused-but-set-variable]
   99 |  auto t3 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:115:7: warning: variable 't4' set but not used [-Wunused-but-set-variable]
  115 |  auto t4 = chrono::high_resolution_clock::now();
      |       ^~
diameter.cpp:125:6: warning: unused variable 'mxd' [-Wunused-variable]
  125 |  int mxd = 0;
      |      ^~~
diameter.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d%d%lld", &edges[i].a, &edges[i].b, &edges[i].w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:67:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |    scanf("%d%lld", &edge_id, &new_weight);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   scanf("%d%lld", &edge_id, &new_weight);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...