제출 #895208

#제출 시각아이디문제언어결과실행 시간메모리
895208fanwenDynamic Diameter (CEOI19_diameter)C++17
24 / 100
164 ms54572 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define file(name) \ if(fopen(name".inp", "r")) \ freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); template <class T> T max(T a, T b, T c) { return max(a, max(b, c)); } const int MAX = 1e5 + 5; struct edge { int u, v; long long w; edge(int u = 0, int v = 0, long long w = 0) : u(u), v(v), w(w) {} int get(int x) { return u ^ x ^ v; } } e[MAX]; int n, q, m, time_in[MAX], time_out[MAX]; vector <int> adj[MAX]; long long W, last; struct info { long long max_depth, min_depth, diam, limp, rimp; info(long long max_depth = 0, long long min_depth = 0, long long diam = 0, long long limp = 0, long long rimp = 0) : max_depth(max_depth), min_depth(min_depth), diam(diam), limp(limp), rimp(rimp) {} }; info operator + (const info &lhs, const info &rhs) { info ans; ans.max_depth = max(lhs.max_depth, rhs.max_depth); ans.min_depth = min(lhs.min_depth, rhs.min_depth); ans.limp = max(lhs.limp, rhs.limp, lhs.max_depth - 2 * rhs.min_depth); ans.rimp = max(lhs.rimp, rhs.rimp, rhs.max_depth - 2 * lhs.min_depth); ans.diam = max(lhs.diam, rhs.diam); ans.diam = max(ans.diam, lhs.max_depth + rhs.rimp, rhs.max_depth + lhs.limp); return ans; } info it[4 * MAX]; long long lazy[4 * MAX]; void apply(int idx, long long val) { info &p = it[idx]; p.max_depth += val; p.min_depth += val; p.limp -= val; p.rimp -= val; lazy[idx] += val; } void push(int p) { if(lazy[p] == 0) return; apply(p << 1, lazy[p]); apply(p << 1 | 1, lazy[p]); lazy[p] = 0; } void update(int idx, int l, int r, int u, int v, long long val) { if(l > v || r < u) return; if(l >= u && r <= v) return apply(idx, val); push(idx); int mid = l + r >> 1; update(idx << 1, l, mid, u, v, val); update(idx << 1 | 1, mid + 1, r, u, v, val); it[idx] = it[idx << 1] + it[idx << 1 | 1]; } void dfs(int u, int p) { static int run = 0; run++; for (int i : adj[u]) if(e[i].get(u) != p) { int v = e[i].get(u); time_in[i] = run; dfs(v, u); time_out[i] = run++; update(1, 1, 2 * n, time_in[i] + 1, time_out[i], e[i].w); } } void you_make_it(void) { cin >> n >> q >> W; for (int i = 1; i < n; ++i) { cin >> e[i].u >> e[i].v >> e[i].w; adj[e[i].u].push_back(i); adj[e[i].v].push_back(i); } dfs(1, 0); while(q--) { int d; long long f; cin >> d >> f; d = (d + last % (n - 1)) % (n - 1) + 1; f = (f + last) % W; update(1, 1, 2 * n, time_in[d] + 1, time_out[d], - e[d].w); e[d].w = f; update(1, 1, 2 * n, time_in[d] + 1, time_out[d], + e[d].w); cout << (last = it[1].diam) << '\n'; } } signed main() { #ifdef LOCAL freopen("TASK.inp", "r", stdin); freopen("TASK.out", "w", stdout); #endif file("diameter"); auto start_time = chrono::steady_clock::now(); cin.tie(0), cout.tie(0) -> sync_with_stdio(0); you_make_it(); auto end_time = chrono::steady_clock::now(); cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl; return (0 ^ 0); } // Dream it. Wish it. Do it.

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

diameter.cpp: In function 'void update(int, int, int, int, int, long long int)':
diameter.cpp:79:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     int mid = l + r >> 1;
      |               ~~^~~
diameter.cpp: In function 'int main()':
diameter.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:127:5: note: in expansion of macro 'file'
  127 |     file("diameter");
      |     ^~~~
diameter.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:127:5: note: in expansion of macro 'file'
  127 |     file("diameter");
      |     ^~~~
#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...