oj.uz

답안 #768262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
768262 2023-06-27T20:17:16 Z hazzle Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 2350 ms 162880 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("avx2")

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;

template <typename T>
using prq = priority_queue <T>;

template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;

template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }

struct segt{
      int n;
      vec <ll> t, p;
      segt() {}
      segt(int n): n(n), t(4 * n), p(4 * n) {}

      void build(int tl, int tr, int v, vec <ll> &d){
            if (tl + 1 == tr) return void(t[v] = d[tl]);
            int tm = tl + tr >> 1;
            build(tl, tm, v * 2 + 1, d);
            build(tm, tr, v * 2 + 2, d);
            t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
      }
      void build(vec <ll> &d){
            build(0, n, 0, d);
      }
      void apply(int v, ll x){
            t[v] += x, p[v] += x;
      }
      void push(int v){
            for (int i: {v * 2 + 1, v * 2 + 2}){
                  apply(i, p[v]);
            }
            p[v] = 0;
      }
      void upd(int l, int r, ll x, int tl, int tr, int v){
            if (l >= r) return;
            if (tl == l && tr == r) return void(apply(v, x));
            push(v);
            int tm = tl + tr >> 1;
            upd(l, min(tm, r), x, tl, tm, v * 2 + 1);
            upd(max(l, tm), r, x, tm, tr, v * 2 + 2);
            t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
      }
      void upd(int l, int r, ll x){
            upd(l, r, x, 0, n, 0);
      }
      ll get(int l, int r, int tl, int tr, int v){
            if (l >= r) return 0LL;
            if (tl == l && tr == r) return t[v];
            push(v);
            int tm = tl + tr >> 1;
            return max(get(l, min(tm, r), tl, tm, v * 2 + 1),
                       get(max(l, tm), r, tm, tr, v * 2 + 2));
      }
      ll get(int l, int r){
            return get(l, r, 0, n, 0);
      }
};

const int N = 1e5 + 42;

vec <pii> g[N];
int us[N], ss[N];

void siz(int u, int p){
      ss[u] = 1;
      for (auto &[v, id]: g[u]) if (v != p && !us[v]){
            siz(v, u), ss[u] += ss[v];
      }
}

int _cen(int u, int p, int n){
      for (auto &[v, id]: g[u]) if (v != p && !us[v]){
            if (2 * ss[v] > n){
                  return _cen(v, u, n);
            }
      }
      return u;
}

int cen(int u){
      siz(u, u);
      return _cen(u, u, ss[u]);
}

ll w[N];
vec <array <int, 4>> ed[N];
multiset <ll, greater <ll>> val[N], s;
segt t[N];
vec <pii> sub[N];

ll get(int u, int i){
      return t[u].get(sub[u][i].fi, sub[u][i].se);
}

ll diam(int u){
      ll res = 0;
      auto it = val[u].begin();
      for (int i = 0; it != val[u].end() && i < 2; ++i, ++it){
            res += *it;
      }
      return res;
}

void upd(int u, int i, int l, int r, ll x){
      s.erase(s.find(diam(u)));
      val[u].erase(val[u].find(get(u, i)));
      t[u].upd(l, r, x);
      val[u].insert(get(u, i));
      s.insert(diam(u));
}

int fi[N], fo[N];
int tmr = 0;
void dfs(int u, int p, int c, int pt, ll h, vec <ll> &d){
      fi[u] = tmr++;
      d.push_back(h);
      for (auto &[v, id]: g[u]) if (v != p && !us[v]){
            dfs(v, u, c, pt, h + w[id], d);
            ed[id].push_back({c, pt, fi[v], fo[v]});
      }
      fo[u] = tmr;
}

void dec(int u){
      us[u] = 1;
      tmr = 0;
      vec <ll> d;
      for (auto &[v, id]: g[u]) if (!us[v]){
            dfs(v, u, u, sz(sub[u]), w[id], d);
            ed[id].push_back({u, sz(sub[u]), fi[v], fo[v]});
            sub[u].push_back({fi[v], fo[v]});
      }
      if (!d.empty()){
            t[u] = segt(sz(d));
            t[u].build(d);
            for (int i = 0; i < sz(sub[u]); ++i){
                  val[u].insert(get(u, i));
            }
            s.insert(diam(u));
      }
      for (auto &[v, id]: g[u]) if (!us[v]){
            dec(cen(v));
      }
}

inline int solve(){
      int n, q; ll W;
      cin >> n >> q >> W;
      for (int i = 0; i < n - 1; ++i){
            int u, v;
            cin >> u >> v >> w[i], --u, --v;
            g[u].push_back({v, i});
            g[v].push_back({u, i});
      }
      dec(cen(0));
      ll ans = 0;
      while(q--){
            int d; ll e;
            cin >> d >> e;
            d = (d + ans) % (n - 1), e = (e + ans) % W;
            for (auto [c, su, l, r]: ed[d]){
                  upd(c, su, l, r, e - w[d]);
            }
            w[d] = e;
            cout << (ans = *s.begin()) << "\n";
      }
      return 0;
}

inline void precalc(){}

signed main(){
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      int tst = 1; //cin >> tst;
      precalc();
      while(tst--) solve();
      return 0;
}

Compilation message

diameter.cpp: In member function 'void segt::build(int, int, int, std::vector<long long int>&)':
diameter.cpp:43:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~
diameter.cpp: In member function 'void segt::upd(int, int, ll, int, int, int)':
diameter.cpp:64:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~
diameter.cpp: In member function 'll segt::get(int, int, int, int, int)':
diameter.cpp:76:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 17480 KB Output is correct
2 Correct 8 ms 17492 KB Output is correct
3 Correct 8 ms 17492 KB Output is correct
4 Correct 8 ms 17492 KB Output is correct
5 Correct 8 ms 17564 KB Output is correct
6 Correct 8 ms 17492 KB Output is correct
7 Correct 8 ms 17568 KB Output is correct
8 Correct 8 ms 17544 KB Output is correct
9 Correct 8 ms 17560 KB Output is correct
10 Correct 8 ms 17492 KB Output is correct
11 Correct 8 ms 17492 KB Output is correct
12 Correct 8 ms 17492 KB Output is correct
13 Correct 9 ms 17504 KB Output is correct
14 Correct 8 ms 17492 KB Output is correct
15 Correct 9 ms 17620 KB Output is correct
16 Correct 8 ms 17596 KB Output is correct
17 Correct 9 ms 17492 KB Output is correct
18 Correct 8 ms 17620 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 17480 KB Output is correct
2 Correct 8 ms 17492 KB Output is correct
3 Correct 8 ms 17492 KB Output is correct
4 Correct 8 ms 17492 KB Output is correct
5 Correct 8 ms 17564 KB Output is correct
6 Correct 8 ms 17492 KB Output is correct
7 Correct 8 ms 17568 KB Output is correct
8 Correct 8 ms 17544 KB Output is correct
9 Correct 8 ms 17560 KB Output is correct
10 Correct 8 ms 17492 KB Output is correct
11 Correct 8 ms 17492 KB Output is correct
12 Correct 8 ms 17492 KB Output is correct
13 Correct 9 ms 17504 KB Output is correct
14 Correct 8 ms 17492 KB Output is correct
15 Correct 9 ms 17620 KB Output is correct
16 Correct 8 ms 17596 KB Output is correct
17 Correct 9 ms 17492 KB Output is correct
18 Correct 8 ms 17620 KB Output is correct
19 Correct 20 ms 18184 KB Output is correct
20 Correct 23 ms 18228 KB Output is correct
21 Correct 24 ms 18260 KB Output is correct
22 Correct 23 ms 18540 KB Output is correct
23 Correct 32 ms 20916 KB Output is correct
24 Correct 38 ms 21872 KB Output is correct
25 Correct 41 ms 22524 KB Output is correct
26 Correct 40 ms 23404 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 17492 KB Output is correct
2 Correct 8 ms 17492 KB Output is correct
3 Correct 9 ms 17492 KB Output is correct
4 Correct 17 ms 17592 KB Output is correct
5 Correct 52 ms 17928 KB Output is correct
6 Correct 9 ms 17576 KB Output is correct
7 Correct 9 ms 17608 KB Output is correct
8 Correct 9 ms 17684 KB Output is correct
9 Correct 10 ms 17620 KB Output is correct
10 Correct 23 ms 17748 KB Output is correct
11 Correct 73 ms 18144 KB Output is correct
12 Correct 11 ms 18644 KB Output is correct
13 Correct 11 ms 18624 KB Output is correct
14 Correct 13 ms 18632 KB Output is correct
15 Correct 28 ms 18772 KB Output is correct
16 Correct 96 ms 19112 KB Output is correct
17 Correct 77 ms 39384 KB Output is correct
18 Correct 77 ms 39376 KB Output is correct
19 Correct 79 ms 39360 KB Output is correct
20 Correct 104 ms 39392 KB Output is correct
21 Correct 243 ms 39572 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 18260 KB Output is correct
2 Correct 27 ms 18328 KB Output is correct
3 Correct 98 ms 18588 KB Output is correct
4 Correct 188 ms 18744 KB Output is correct
5 Correct 27 ms 28372 KB Output is correct
6 Correct 55 ms 28428 KB Output is correct
7 Correct 203 ms 28604 KB Output is correct
8 Correct 328 ms 28916 KB Output is correct
9 Correct 105 ms 79828 KB Output is correct
10 Correct 152 ms 79896 KB Output is correct
11 Correct 373 ms 79864 KB Output is correct
12 Correct 658 ms 80188 KB Output is correct
13 Correct 232 ms 148584 KB Output is correct
14 Correct 285 ms 148596 KB Output is correct
15 Correct 597 ms 148680 KB Output is correct
16 Correct 963 ms 148696 KB Output is correct
17 Correct 1974 ms 148668 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1698 ms 121792 KB Output is correct
2 Correct 1782 ms 124960 KB Output is correct
3 Correct 1757 ms 123916 KB Output is correct
4 Correct 1791 ms 124704 KB Output is correct
5 Correct 1711 ms 118164 KB Output is correct
6 Correct 1415 ms 84512 KB Output is correct
7 Correct 2268 ms 151120 KB Output is correct
8 Correct 2263 ms 150992 KB Output is correct
9 Correct 2214 ms 151120 KB Output is correct
10 Correct 2265 ms 150372 KB Output is correct
11 Correct 2162 ms 142456 KB Output is correct
12 Correct 1816 ms 99660 KB Output is correct
13 Correct 2229 ms 162812 KB Output is correct
14 Correct 2202 ms 162772 KB Output is correct
15 Correct 2128 ms 162812 KB Output is correct
16 Correct 2219 ms 162128 KB Output is correct
17 Correct 2135 ms 153476 KB Output is correct
18 Correct 1699 ms 105004 KB Output is correct
19 Correct 2197 ms 162832 KB Output is correct
20 Correct 2171 ms 162880 KB Output is correct
21 Correct 2216 ms 162736 KB Output is correct
22 Correct 2181 ms 162016 KB Output is correct
23 Correct 2074 ms 153492 KB Output is correct
24 Correct 1736 ms 105068 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 17480 KB Output is correct
2 Correct 8 ms 17492 KB Output is correct
3 Correct 8 ms 17492 KB Output is correct
4 Correct 8 ms 17492 KB Output is correct
5 Correct 8 ms 17564 KB Output is correct
6 Correct 8 ms 17492 KB Output is correct
7 Correct 8 ms 17568 KB Output is correct
8 Correct 8 ms 17544 KB Output is correct
9 Correct 8 ms 17560 KB Output is correct
10 Correct 8 ms 17492 KB Output is correct
11 Correct 8 ms 17492 KB Output is correct
12 Correct 8 ms 17492 KB Output is correct
13 Correct 9 ms 17504 KB Output is correct
14 Correct 8 ms 17492 KB Output is correct
15 Correct 9 ms 17620 KB Output is correct
16 Correct 8 ms 17596 KB Output is correct
17 Correct 9 ms 17492 KB Output is correct
18 Correct 8 ms 17620 KB Output is correct
19 Correct 20 ms 18184 KB Output is correct
20 Correct 23 ms 18228 KB Output is correct
21 Correct 24 ms 18260 KB Output is correct
22 Correct 23 ms 18540 KB Output is correct
23 Correct 32 ms 20916 KB Output is correct
24 Correct 38 ms 21872 KB Output is correct
25 Correct 41 ms 22524 KB Output is correct
26 Correct 40 ms 23404 KB Output is correct
27 Correct 8 ms 17492 KB Output is correct
28 Correct 8 ms 17492 KB Output is correct
29 Correct 9 ms 17492 KB Output is correct
30 Correct 17 ms 17592 KB Output is correct
31 Correct 52 ms 17928 KB Output is correct
32 Correct 9 ms 17576 KB Output is correct
33 Correct 9 ms 17608 KB Output is correct
34 Correct 9 ms 17684 KB Output is correct
35 Correct 10 ms 17620 KB Output is correct
36 Correct 23 ms 17748 KB Output is correct
37 Correct 73 ms 18144 KB Output is correct
38 Correct 11 ms 18644 KB Output is correct
39 Correct 11 ms 18624 KB Output is correct
40 Correct 13 ms 18632 KB Output is correct
41 Correct 28 ms 18772 KB Output is correct
42 Correct 96 ms 19112 KB Output is correct
43 Correct 77 ms 39384 KB Output is correct
44 Correct 77 ms 39376 KB Output is correct
45 Correct 79 ms 39360 KB Output is correct
46 Correct 104 ms 39392 KB Output is correct
47 Correct 243 ms 39572 KB Output is correct
48 Correct 11 ms 18260 KB Output is correct
49 Correct 27 ms 18328 KB Output is correct
50 Correct 98 ms 18588 KB Output is correct
51 Correct 188 ms 18744 KB Output is correct
52 Correct 27 ms 28372 KB Output is correct
53 Correct 55 ms 28428 KB Output is correct
54 Correct 203 ms 28604 KB Output is correct
55 Correct 328 ms 28916 KB Output is correct
56 Correct 105 ms 79828 KB Output is correct
57 Correct 152 ms 79896 KB Output is correct
58 Correct 373 ms 79864 KB Output is correct
59 Correct 658 ms 80188 KB Output is correct
60 Correct 232 ms 148584 KB Output is correct
61 Correct 285 ms 148596 KB Output is correct
62 Correct 597 ms 148680 KB Output is correct
63 Correct 963 ms 148696 KB Output is correct
64 Correct 1974 ms 148668 KB Output is correct
65 Correct 1698 ms 121792 KB Output is correct
66 Correct 1782 ms 124960 KB Output is correct
67 Correct 1757 ms 123916 KB Output is correct
68 Correct 1791 ms 124704 KB Output is correct
69 Correct 1711 ms 118164 KB Output is correct
70 Correct 1415 ms 84512 KB Output is correct
71 Correct 2268 ms 151120 KB Output is correct
72 Correct 2263 ms 150992 KB Output is correct
73 Correct 2214 ms 151120 KB Output is correct
74 Correct 2265 ms 150372 KB Output is correct
75 Correct 2162 ms 142456 KB Output is correct
76 Correct 1816 ms 99660 KB Output is correct
77 Correct 2229 ms 162812 KB Output is correct
78 Correct 2202 ms 162772 KB Output is correct
79 Correct 2128 ms 162812 KB Output is correct
80 Correct 2219 ms 162128 KB Output is correct
81 Correct 2135 ms 153476 KB Output is correct
82 Correct 1699 ms 105004 KB Output is correct
83 Correct 2197 ms 162832 KB Output is correct
84 Correct 2171 ms 162880 KB Output is correct
85 Correct 2216 ms 162736 KB Output is correct
86 Correct 2181 ms 162016 KB Output is correct
87 Correct 2074 ms 153492 KB Output is correct
88 Correct 1736 ms 105068 KB Output is correct
89 Correct 1692 ms 122712 KB Output is correct
90 Correct 1925 ms 134064 KB Output is correct
91 Correct 2207 ms 147140 KB Output is correct
92 Correct 2348 ms 150856 KB Output is correct
93 Correct 2254 ms 155536 KB Output is correct
94 Correct 2209 ms 159104 KB Output is correct
95 Correct 2183 ms 162632 KB Output is correct
96 Correct 2201 ms 162656 KB Output is correct
97 Correct 2266 ms 162860 KB Output is correct
98 Correct 2350 ms 162656 KB Output is correct
99 Correct 2312 ms 162696 KB Output is correct
100 Correct 2154 ms 162724 KB Output is correct