제출 #618894

#제출 시각아이디문제언어결과실행 시간메모리
618894juancarlovieriDynamic Diameter (CEOI19_diameter)C++17
11 / 100
5071 ms19732 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int long long #define sm (ss + se) / 2 #define time mytime void myassert(bool a) { while(!a); } int time = -1; ll tree[400005]; ll pend[400004]; vector<pair<int, int>> edge[100005]; int depth[100005]; int in[100005], out[100005]; int par[100005]; int old[100005]; void push(int i, int ss, int se) { if (pend[i] != 0) { tree[i] += pend[i]; if (ss != se) { pend[i * 2] += pend[i]; pend[i * 2 + 1] += pend[i]; } pend[i] = 0; } } // void upd(int l, int r, int val, int ss = 0, int se = 100000, int i = 1) { // myassert(l <= r); // push(i, ss, se); // if (ss > se or r < ss or l > se) return; // if (l <= ss and r >= se) { // pend[i] += val; // push(i, ss, se); // return; // } // upd(l, r, val, ss, sm, i * 2); // upd(l, r, val, sm + 1, se, i * 2 + 1); // tree[i] = max(tree[i * 2], tree[i * 2 + 1]); // } // int get(int l, int r, int ss = 0, int se = 100000, int i = 1) { // myassert(l <= r); // push(i, ss, se); // if (ss > se or ss > r or se < l) return 0; // if (ss >= l and se <= r) { // return tree[i]; // } // return max(get(l, r, ss, sm, i * 2), get(l, r, sm + 1, se, i * 2 + 1)); // } int get(int l, int r) { int ans = 0; for (int i = l; i <= r; ++i) ans = max(ans, tree[i]); return ans; } void upd(int l, int r, int val) { for (int i = l; i <= r; ++i) tree[i] += val; } void rek(int cur, int prev = -1) { ++time; in[cur] = time; for (auto [i, w] : edge[cur]) { if (i == prev) continue; depth[i] = depth[cur] + w; par[i] = cur; rek(i, cur); } out[cur] = time; } int getmaks(int i) { if (edge[i].empty()) return 0; int lo = 0, hi = edge[i].size(); int maks = get(in[i], out[i]); while (lo <= hi) { int mid = (lo + hi) / 2; if (get(in[i], out[edge[i][mid].first]) == maks) { hi = mid - 1; } else lo = mid + 1; } int maks2 = 0; if (lo) maks2 = max(maks2, get(in[i], out[edge[i][lo - 1].first])); if (lo + 1 < edge[i].size()) maks2 = max(maks2, get(in[edge[i][lo + 1].first], out[i])); // cout << maks << ' ' << maks2 << get(in[i], in[i]) << ' ' << endl; // cout << maks + maks2 - get(in[i], in[i]) - get(in[i], in[i]) << endl; int par = get(in[i], in[i]); return maks - par + maks2 - (maks2 ? par : 0); } signed main() { int n, q, w; cin >> n >> q >> w; vector<pair<pair<int, int>, int>> edges; for (int i = 0; i < n - 1; ++i) { int u, v, w; cin >> u >> v >> w; --u, --v; edge[u].push_back({v, w}); edge[v].push_back({u, w}); edges.push_back({{u, v}, w}); } memset(par, -1, sizeof par); rek(0); for (int i = 0; i < n; ++i) { // cout << depth[i] << ' '; // upd(in[i], out[i], depth[i]); for (auto [j, w] : edge[i]) { if (in[j] < in[i]) continue; // cout << in[j] << ' ' << out[j] << ' ' << w << endl; upd(in[j], out[j], w); } for (int j = 0; j < edge[i].size(); ++j) { if (edge[i][j].first == par[i]) { // cout << i << ' ' << par[i] << endl; edge[i].erase(edge[i].begin() + j); break; } } } // cout << in[2] << ' ' << out[2] << endl; // cout << getmaks(2) << endl; // return 0; multiset<int> all; for (int i = 0; i < n; ++i) { // cout << getmaks(i) << ' '; old[i] = getmaks(i); all.insert(old[i]); } // cout << endl; // return 0; int last = 0; // cout << get(3, 3) << endl; while (q--) { int d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % w; // cout << "REal " << d << ' ' << e << endl; auto prev = edges[d]; edges[d].second = e; auto [u, v] = prev.first; if (in[u] > in[v]) swap(u, v); int cur = u; // for (auto i : all) cout << i << ' '; // cout << endl; while(cur != -1) { // cout << getmaks(cur) << endl; all.erase(all.find(old[cur])); cur = par[cur]; } // cout << in[v] << ' ' << out[v] << ' ' << e - prev.second << endl; upd(in[v], out[v], e - prev.second); cur = u; while(cur != -1) { old[cur] = getmaks(cur); all.insert(old[cur]); cur = par[cur]; } // cout << maks << endl; // cout << maks + maks2 << endl; // last = getmaks(0); auto it = all.end(); --it; last = (*it); // last = 0; // for (int i = 0; i < n; ++i) last = max(last, getmaks(i)); cout << last << endl; } }

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

diameter.cpp: In function 'long long int getmaks(long long int)':
diameter.cpp:91:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   if (lo + 1 < edge[i].size()) maks2 = max(maks2, get(in[edge[i][lo + 1].first], out[i]));
      |       ~~~~~~~^~~~~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:121:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (int j = 0; j < edge[i].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~~~
#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...