Submission #730305

#	Time	Username	Problem	Language	Result	Execution time	Memory
730305		MilosMilutinovic	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	4639 ms	201428 KiB

diameter

/**
 *    author:  wxhtzdy
 *    created: 25.04.2023 16:05:28
**/
#include <bits/stdc++.h>

using namespace std;

struct segtree {
  vector<long long> mx;
  vector<long long> lzy;
  segtree(int n) {
    mx.resize(4 * n);
    lzy.resize(4 * n);
    fill(mx.begin(), mx.end(), 0);
    fill(lzy.begin(), lzy.end(), 0);
  }
  void push(int v) {
    if (2 * v + 1 < mx.size()) {
      mx[2 * v] += lzy[v];
      mx[2 * v + 1] += lzy[v];
      lzy[2 * v] += lzy[v];
      lzy[2 * v + 1] += lzy[v];
    }
    lzy[v] = 0;
  }
  void modify(int v, int l, int r, int ql, int qr, long long x) {
    if (l > qr || r < ql || l > r) {
      return;
    }
    if (ql <= l && r <= qr) {
      lzy[v] += x;
      mx[v] += x;
      push(v);
      return;
    }
    push(v);
    int mid = l + r >> 1;
    modify(2 * v, l, mid, ql, qr, x);
    modify(2 * v + 1, mid + 1, r, ql, qr, x);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
  }
  long long query(int v, int l, int r, int ql, int qr) {
    if (l > qr || r < ql || l > r) {
      return 0LL;
    }
    if (ql <= l && r <= qr) {
      return mx[v];
    }
    push(v);
    int mid = l + r >> 1;
    long long L = query(2 * v, l, mid, ql, qr);
    long long R = query(2 * v + 1, mid + 1, r, ql, qr);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
    return max(L, R); 
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, q;
  long long W;
  cin >> n >> q >> W;
  vector<vector<pair<int, int>>> g(n);
  vector<int> u(n), v(n);
  vector<long long> w(n);
  for (int i = 0; i < n - 1; i++) {
    cin >> u[i] >> v[i] >> w[i];
    --u[i]; --v[i];
    g[u[i]].emplace_back(v[i], i);
    g[v[i]].emplace_back(u[i], i);    
  }
  vector<bool> rem(n);
  vector<int> sz(n);
  function<void(int, int)> DfsSz = [&](int v, int pv) {
    sz[v] = 1;
    for (auto& p : g[v]) {
      int u = p.first;   
      if (u == pv || rem[u]) {
        continue;
      }
      DfsSz(u, v);
      sz[v] += sz[u];
    }
  };
  function<int(int, int, int)> Cen = [&](int v, int pv, int n) {
    for (auto& p : g[v]) {
      int u = p.first;
      if (u == pv || rem[u] || sz[u] * 2 < n) {
        continue;
      }
      return Cen(u, v, n);
    }
    return v;
  };
  int T;
  vector<vector<int>> tin(n);
  vector<vector<int>> tout(n);
  vector<vector<int>> ids(n);
  vector<vector<int>> sub(n);
  function<void(int, int, int, int)> Dfs = [&](int v, int pv, int cp, int sp) {
    tin[v].push_back(++T);
    sub[v].push_back(sp);
    for (auto& p : g[v]) {
      int u = p.first;
      int i = p.second;
      if (u == pv || rem[u]) {
        continue;
      }
      ids[i].push_back(cp);
      Dfs(u, v, cp, (v == cp ? u : sp));
    }
    tout[v].push_back(T);
  };
  vector<segtree> st(n, segtree(1)); 
  vector<int> len(n);
  vector<vector<int>> ch(n);
  vector<int> dep(n);
  function<void(int, int)> Decompose = [&](int v, int d) {
    DfsSz(v, v);
    v = Cen(v, v, sz[v]);
    dep[v] = d;
    T = -1;
    Dfs(v, v, v, v);
    len[v] = T;
    st[v] = segtree(T + 1);
    rem[v] = true;
    for (auto& p : g[v]) {
      int u = p.first;
      if (!rem[u]) {
        ch[v].push_back(u);
        Decompose(u, d + 1);
      }
    }  
  };
  Decompose(0, 0);
  for (int i = 0; i < n - 1; i++) {
    for (int cp : ids[i]) {
      if (tin[u[i]][dep[cp]] > tin[v[i]][dep[cp]]) {
        swap(u[i], v[i]);
      }
      st[cp].modify(1, 0, len[cp], tin[v[i]][dep[cp]], tout[v[i]][dep[cp]], w[i]);
    }
  }
  multiset<long long> all;
  vector<multiset<long long>> my(n);
  auto Calc = [&](int v) {
    long long s = 0;
    auto it = my[v].end();
    for (int rep = 0; rep < 2; rep++) {
      if (it == my[v].begin()) {
        break;
      }
      it = prev(it);
      s += *it;
    }
    return s;
  };
  for (int i = 0; i < n; i++) {
    my[i].insert(0);
    for (int j : ch[i]) {
      my[i].insert(st[i].query(1, 0, len[i], tin[j][dep[i]], tout[j][dep[i]]));      
    }
    all.insert(Calc(i));
  }
  long long last = 0;
  while (q--) {
    int d;
    long long e;
    cin >> d >> e;
    d = (d + last) % (n - 1);
    e = (e + last) % W;
    for (int cp : ids[d]) {
      all.erase(all.find(Calc(cp)));               
      if (tin[u[d]][dep[cp]] > tin[v[d]][dep[cp]]) {
        swap(u[d], v[d]);  
      }
      my[cp].erase(my[cp].find(st[cp].query(1, 0, len[cp], tin[sub[v[d]][dep[cp]]][dep[cp]], tout[sub[v[d]][dep[cp]]][dep[cp]])));
      st[cp].modify(1, 0, len[cp], tin[v[d]][dep[cp]], tout[v[d]][dep[cp]], e - w[d]);
      my[cp].insert(st[cp].query(1, 0, len[cp], tin[sub[v[d]][dep[cp]]][dep[cp]], tout[sub[v[d]][dep[cp]]][dep[cp]]));
      all.insert(Calc(cp));
    }
    w[d] = e;
    last = *prev(all.end());
    cout << last << '\n';
  } 
  return 0;
}

Compilation message (stderr)

diameter.cpp: In member function 'void segtree::push(int)':
diameter.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     if (2 * v + 1 < mx.size()) {
      |         ~~~~~~~~~~^~~~~~~~~~~
diameter.cpp: In member function 'void segtree::modify(int, int, int, int, int, long long int)':
diameter.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = l + r >> 1;
      |               ~~^~~
diameter.cpp: In member function 'long long int segtree::query(int, int, int, int, int)':
diameter.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = l + r >> 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