Submission #768262

#	Time	Username	Problem	Language	Result	Execution time	Memory
768262		hazzle	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	2350 ms	162880 KiB

diameter

#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 (stderr)

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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27