제출 #902524

#제출 시각아이디문제언어결과실행 시간메모리
902524fanwenDynamic Diameter (CEOI19_diameter)C++17
100 / 100
730 ms49216 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)); } template <class T, class U> struct lazy_segment_tree { int n, size, log; vector<T> d; vector<U> lazy; function <T(T, T)> TT; function <T(U, T)> UT; function <U(U, U)> UU; T T_id; U U_id; lazy_segment_tree(){} lazy_segment_tree(const vector<T>& v, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(v); } lazy_segment_tree(int n, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, T_id); } lazy_segment_tree(int n, T x, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, x); } void init(int n, T x) { this->n = n; log = __lg(max(n - 1, 1)) + 1, size = 1 << log; d = vector<T>(2 * size, T_id); lazy = vector<U>(size, U_id); for (int i = 0; i < n; i++) d[size + i] = x; for (int i = size - 1; i >= 1; i--) { update(i); } } void init(const vector <T> &v) { n = (int) v.size(); log = __lg(max(n - 1, 1)) + 1, size = 1 << log; d = vector<T>(2 * size, T_id); lazy = vector<U>(size, U_id); for (int i = 0; i < n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void update(int k) { d[k] = TT(d[k << 1], d[k << 1 | 1]); } void apply(int k, U f) { d[k] = UT(f, d[k]); if (k < size) lazy[k] = UU(f, lazy[k]); } void push(int k) { apply(k << 1, lazy[k]); apply(k << 1 | 1, lazy[k]); lazy[k] = U_id; } void set(int p, T x) { assert(0 <= p && p < n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } T get(int p) { assert(0 <= p && p < n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } T get(int l, int r) { assert(0 <= l && l <= r && r <= n); if (l == r) return T_id; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } T sml = T_id, smr = T_id; while (l < r) { if (l & 1) sml = TT(sml, d[l++]); if (r & 1) smr = TT(d[--r], smr); l >>= 1; r >>= 1; } return TT(sml, smr); } T get_all() { return d[1]; } void update(int p, U f) { assert(0 <= p && p < n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = UT(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void update(int l, int r, U f) { assert(0 <= l && l <= r && r <= n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) apply(l++, f); if (r & 1) apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template <bool (*g)(T)> int max_right(int l) { return max_right(l, [](T x) { return g(x); }); } template <class G> int max_right(int l, G g) { assert(0 <= l && l <= n); assert(g(T_id)); if (l == n) return n; l += size; for (int i = log; i >= 1; i--) push(l >> i); T sm = T_id; do { while (l % 2 == 0) l >>= 1; if (!g(TT(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(TT(sm, d[l]))) { sm = TT(sm, d[l]); l++; } } return l - size; } sm = TT(sm, d[l]); l++; } while ((l & -l) != l); return n; } template <bool (*g)(T)> int min_left(int r) { return min_left(r, [](T x) { return g(x); }); } template <class G> int min_left(int r, G g) { assert(0 <= r && r <= n); assert(g(T_id)); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); T sm = T_id; do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(TT(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(TT(d[r], sm))) { sm = TT(d[r], sm); r--; } } return r + 1 - size; } sm = TT(d[r], sm); } while ((r & -r) != r); return 0; } friend ostream & operator << (ostream &out, const lazy_segment_tree &seg) { out << "["; for (int i = 0; i < seg.n; ++i) { out << seg.get(i); if(i + 1 < seg.n) out << ", "; } return out << "]"; }; }; const int MAX = 2e5 + 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 T { long long max_depth, min_depth, diam, limp, rimp; T(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) {} }; T TT(const T &lhs, const T &rhs) { T 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; } auto UT = [] (const long long &val, const T &lhs) { return T(lhs.max_depth + val, lhs.min_depth + val, lhs.diam, lhs.limp - val, lhs.rimp - val); }; auto UU = [](long long a, long long b) { return a + b; }; lazy_segment_tree <T, long long> it; 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++; it.update(time_in[i], 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); } it = lazy_segment_tree <T, long long> (2 * n, TT, UU, UT, T(), 0); 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; it.update(time_in[d], time_out[d], - e[d].w); e[d].w = f; it.update(time_in[d], time_out[d], + e[d].w); cout << (last = it.get_all().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:26:43: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   26 |     lazy_segment_tree(const vector<T>& v, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(v); }
      |                                           ^~~~
diameter.cpp:26:52: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   26 |     lazy_segment_tree(const vector<T>& v, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(v); }
      |                                                    ^~~~
diameter.cpp:26:61: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   26 |     lazy_segment_tree(const vector<T>& v, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(v); }
      |                                                             ^~~~
diameter.cpp:27:30: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 |     lazy_segment_tree(int n, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, T_id); }
      |                              ^~~~
diameter.cpp:27:39: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 |     lazy_segment_tree(int n, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, T_id); }
      |                                       ^~~~
diameter.cpp:27:48: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 |     lazy_segment_tree(int n, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, T_id); }
      |                                                ^~~~
diameter.cpp:28:35: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   28 |     lazy_segment_tree(int n, T x, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, x); }
      |                                   ^~~~
diameter.cpp:28:44: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   28 |     lazy_segment_tree(int n, T x, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, x); }
      |                                            ^~~~
diameter.cpp:28:53: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   28 |     lazy_segment_tree(int n, T x, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, x); }
      |                                                     ^~~~
diameter.cpp: In instantiation of 'lazy_segment_tree<T, U>::lazy_segment_tree(int, auto:26, auto:27, auto:28, T, U) [with auto:26 = T (*)(const T&, const T&); auto:27 = <lambda(long long int, long long int)>; auto:28 = <lambda(const long long int&, const T&)>; T = T; U = long long int]':
diameter.cpp:281:69:   required from here
diameter.cpp:22:24: warning: 'lazy_segment_tree<T, long long int>::UU' will be initialized after [-Wreorder]
   22 |     function <U(U, U)> UU;
      |                        ^~
diameter.cpp:21:24: warning:   'std::function<T(long long int, T)> lazy_segment_tree<T, long long int>::UT' [-Wreorder]
   21 |     function <T(U, T)> UT;
      |                        ^~
diameter.cpp:27:5: warning:   when initialized here [-Wreorder]
   27 |     lazy_segment_tree(int n, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, T_id); }
      |     ^~~~~~~~~~~~~~~~~
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:303:5: note: in expansion of macro 'file'
  303 |     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:303:5: note: in expansion of macro 'file'
  303 |     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...