oj.uz

Submission #768257

# Submission time Handle Problem Language Result Execution time Memory
768257 2023-06-27T19:59:53 Z hazzle Dynamic Diameter (CEOI19_diameter) C++17
42 / 100
 2440 ms 168548 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){
//            cout << "BUILD" << tl << " " << tr << "\n";
            assert(v < sz(t));
            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){
            assert(n == sz(d));
            if (!d.empty()){
                  build(0, n, 0, d);
            }
      }
      void apply(int v, ll x){
            t[v] += x, p[v] += x;
      }
      void push(int v){
            if (p[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){
//            cout << "UPD " << tl << " " << tr << "\n";
            assert(v < sz(t));
            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){
            if (n) upd(l, r, x, 0, n, 0);
      }
      ll get(int l, int r, int tl, int tr, int v){
//            cout << "GET " << tl << " " << tr << "\n";
            assert(v < sz(t));
            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){
            if (!n) return 0LL;
            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){
//      cout << "FUCK " << u << "\n";
      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){
//      cout << "FUCK2 " << u << "\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(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){
//      cout << "FUCK5 " << u << "\n";
      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]});
      }
//      cout << "WHERE\n";
      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));
//      cout << "WTF\n";

      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});
      }
      s = {0LL};
      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:45:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~
diameter.cpp: In member function 'void segt::upd(int, int, ll, int, int, int)':
diameter.cpp:73:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~
diameter.cpp: In member function 'll segt::get(int, int, int, int, int)':
diameter.cpp:87:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17492 KB Output is correct
2 Correct 10 ms 17492 KB Output is correct
3 Correct 9 ms 17564 KB Output is correct
4 Correct 9 ms 17492 KB Output is correct
5 Correct 9 ms 17488 KB Output is correct
6 Correct 9 ms 17492 KB Output is correct
7 Correct 9 ms 17564 KB Output is correct
8 Correct 9 ms 17572 KB Output is correct
9 Correct 9 ms 17492 KB Output is correct
10 Correct 9 ms 17588 KB Output is correct
11 Correct 9 ms 17560 KB Output is correct
12 Correct 10 ms 17560 KB Output is correct
13 Correct 9 ms 17564 KB Output is correct
14 Correct 12 ms 17620 KB Output is correct
15 Correct 10 ms 17508 KB Output is correct
16 Correct 10 ms 17580 KB Output is correct
17 Correct 11 ms 17568 KB Output is correct
18 Correct 10 ms 17620 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17492 KB Output is correct
2 Correct 10 ms 17492 KB Output is correct
3 Correct 9 ms 17564 KB Output is correct
4 Correct 9 ms 17492 KB Output is correct
5 Correct 9 ms 17488 KB Output is correct
6 Correct 9 ms 17492 KB Output is correct
7 Correct 9 ms 17564 KB Output is correct
8 Correct 9 ms 17572 KB Output is correct
9 Correct 9 ms 17492 KB Output is correct
10 Correct 9 ms 17588 KB Output is correct
11 Correct 9 ms 17560 KB Output is correct
12 Correct 10 ms 17560 KB Output is correct
13 Correct 9 ms 17564 KB Output is correct
14 Correct 12 ms 17620 KB Output is correct
15 Correct 10 ms 17508 KB Output is correct
16 Correct 10 ms 17580 KB Output is correct
17 Correct 11 ms 17568 KB Output is correct
18 Correct 10 ms 17620 KB Output is correct
19 Incorrect 33 ms 18264 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17564 KB Output is correct
2 Correct 9 ms 17556 KB Output is correct
3 Correct 12 ms 17572 KB Output is correct
4 Correct 19 ms 17696 KB Output is correct
5 Correct 57 ms 18712 KB Output is correct
6 Correct 9 ms 17492 KB Output is correct
7 Correct 10 ms 17696 KB Output is correct
8 Correct 10 ms 17652 KB Output is correct
9 Correct 11 ms 17704 KB Output is correct
10 Correct 35 ms 17908 KB Output is correct
11 Correct 78 ms 18956 KB Output is correct
12 Correct 15 ms 18876 KB Output is correct
13 Correct 16 ms 18896 KB Output is correct
14 Correct 14 ms 18964 KB Output is correct
15 Correct 30 ms 19196 KB Output is correct
16 Correct 107 ms 20660 KB Output is correct
17 Correct 94 ms 45304 KB Output is correct
18 Correct 101 ms 45328 KB Output is correct
19 Correct 101 ms 45360 KB Output is correct
20 Correct 130 ms 45500 KB Output is correct
21 Correct 342 ms 46232 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18388 KB Output is correct
2 Incorrect 37 ms 18516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1811 ms 128472 KB Output is correct
2 Correct 1977 ms 131660 KB Output is correct
3 Correct 2021 ms 130592 KB Output is correct
4 Correct 1898 ms 131404 KB Output is correct
5 Correct 1900 ms 125140 KB Output is correct
6 Correct 1529 ms 91652 KB Output is correct
7 Correct 2440 ms 157544 KB Output is correct
8 Correct 2410 ms 157756 KB Output is correct
9 Correct 2351 ms 157544 KB Output is correct
10 Correct 2345 ms 157048 KB Output is correct
11 Correct 2355 ms 149076 KB Output is correct
12 Correct 1972 ms 106372 KB Output is correct
13 Correct 2286 ms 168412 KB Output is correct
14 Correct 2235 ms 168456 KB Output is correct
15 Correct 2237 ms 168512 KB Output is correct
16 Correct 2291 ms 167976 KB Output is correct
17 Correct 2219 ms 159408 KB Output is correct
18 Correct 1797 ms 112200 KB Output is correct
19 Correct 2276 ms 168472 KB Output is correct
20 Correct 2252 ms 168420 KB Output is correct
21 Correct 2263 ms 168548 KB Output is correct
22 Correct 2240 ms 168064 KB Output is correct
23 Correct 2166 ms 159720 KB Output is correct
24 Correct 1794 ms 111704 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17492 KB Output is correct
2 Correct 10 ms 17492 KB Output is correct
3 Correct 9 ms 17564 KB Output is correct
4 Correct 9 ms 17492 KB Output is correct
5 Correct 9 ms 17488 KB Output is correct
6 Correct 9 ms 17492 KB Output is correct
7 Correct 9 ms 17564 KB Output is correct
8 Correct 9 ms 17572 KB Output is correct
9 Correct 9 ms 17492 KB Output is correct
10 Correct 9 ms 17588 KB Output is correct
11 Correct 9 ms 17560 KB Output is correct
12 Correct 10 ms 17560 KB Output is correct
13 Correct 9 ms 17564 KB Output is correct
14 Correct 12 ms 17620 KB Output is correct
15 Correct 10 ms 17508 KB Output is correct
16 Correct 10 ms 17580 KB Output is correct
17 Correct 11 ms 17568 KB Output is correct
18 Correct 10 ms 17620 KB Output is correct
19 Incorrect 33 ms 18264 KB Output isn't correct
20 Halted 0 ms 0 KB -