Submission #659931

#	Time	Username	Problem	Language	Result	Execution time	Memory
659931		600Mihnea	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5066 ms	193540 KiB

diameter

bool home = 0;
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = (ll) 1e18 + 7;


struct SegmentTree {
  vector<ll> tree;
  vector<ll> lazy;
  int n;

  void init(int nn) {
    n = nn;
    assert(n >= 1);
    tree.resize(4 * (n + 7), 0);
    lazy.resize(4 * (n + 7), 0);
  }

  void push(int v, int tl, int tr) {
    if (lazy[v]) {
      tree[v] += lazy[v];
      if (tl < tr) {
        lazy[2 * v] += lazy[v];
        lazy[2 * v + 1] += lazy[v];
      }
      lazy[v] = 0;
    }
  }

  void add(int v, int tl, int tr, int l, int r, ll x) {
    push(v, tl, tr);
    if (tr < l || r < tl) {
      return;
    }
    if (l <= tl && tr <= r) {
      lazy[v] += x;
      push(v, tl, tr);
      return;
    }
    int tm = (tl + tr) / 2;
    add(2 * v, tl, tm, l, r, x);
    add(2 * v + 1, tm + 1, tr, l, r, x);
    tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  }

  ll getmax(int v, int tl, int tr, int l, int r) {
    push(v, tl, tr);
    if (tr < l || r < tl) {
      return -INF;
    }
    if (l <= tl && tr <= r) {
      return tree[v];
    }
    int tm = (tl + tr) / 2;
    return max(getmax(2 * v, tl, tm, l, r), getmax(2 * v + 1, tm + 1, tr, l, r));
  }

  void add(int l, int r, ll x) {
    ///cout << "\t\t\t\t add " << l << " " << r << ", " << x << "\n";
    assert(1 <= l && l <= r && r <= n);
    add(1, 1, n, l, r, x);
  }

  ll getmax(int l, int r) {
    assert(1 <= l && l <= r && r <= n);
    ll sol = getmax(1, 1, n, l, r);
   /// cout << " query " << l << " " << r << " : " << sol << "\n";
    return sol;
  }
};

const int N = (int) 1e5 + 7;
const int K = 20;
int n;
int q;
ll w;
int sum_edge[N];
ll val_edge[N];
vector<int> gindex[N];
SegmentTree trees[K];
bool blocked[N];
int sub[N];
int total_under;

void build_sub(int a, int p = -1) {
  sub[a] = 1;
  for (auto &I : gindex[a]) {
    int b = sum_edge[I] - a;
    if (b == p || blocked[b]) {
      continue;
    }
    build_sub(b, a);
    sub[a] += sub[b];
  }
}

int fcen(int a, int p = -1) {
  int mx = total_under - sub[a];
  for (auto &I : gindex[a]) {
    int b = sum_edge[I] - a;
    if (b == p || blocked[b]) {
      continue;
    }
    mx = max(mx, sub[b]);
  }
  if (mx <= total_under / 2) {
    return a;
  }
  for (auto &I : gindex[a]) {
    int b = sum_edge[I] - a;
    if (b == p || blocked[b]) {
      continue;
    }
    if (mx == sub[b]) {
      return fcen(b, a);
    }
  }
  assert(0);
}

int low[K][N];
int high[K][N];
int ord[K][N];
int where[K][N];
int vrt[K][N];
int top[K];

vector<ll> all;
vector<int> where2;
vector<pair<int, int>> seg;
vector<multiset<ll>> s;
int kek = -1;
int kek2 = -1;

multiset<int> tog;

void prep(int a, int p, int level) {
  sub[a] = 1;
  ord[level][++top[level]] = a;
  low[level][a] = top[level];
  for (auto &I : gindex[a]) {
    int b = sum_edge[I] - a;
    if (b == p || blocked[b]) {
      continue;
    }
    where[level][I] = kek;
    vrt[level][I] = b;
    prep(b, a, level);
    sub[a] += sub[b];
  }
  if (kek == 3) {
 ///   cout << "\t\t\t\t" << a << " -> " << low[level][a] << ", " << high[level][a] << "\n";
  }
  high[level][a] = top[level];
}

void add(int i, ll delta) {
  for (int level = 0; level < K; level++) {
    if (level != 0) {
      ///continue; /// delete this line urgently !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    }
    if (where[level][i] == -1) {
      continue;
    }
    int b = vrt[level][i];
    int l = low[level][b], r = high[level][b];

    {
      ll cur = 0;
      auto it = s[where2[where[level][i]]].end();
      it--;
      cur += *it;
      it--;
      cur += *it;
      if (tog.count(cur)) {
        tog.erase(tog.find(cur));
      }
    }
   /* cout << " queeeeeeeeeeeeeeeeeeeeeeeeee " << i << " " << b << "\n";
    cout << where[level][i] << " @ " << i << ", " << level << " : " << where2[where[level][i]] << " | " << seg[where[level][i]].first << " and " << seg[where[level][i]].second << " | " << l << " " << r  << ", the max is ";
    cout << trees[level].getmax(seg[where[level][i]].first, seg[where[level][i]].second) << "\n";
    for (auto &it : s[where2[where[level][i]]]) {
      cout << it << " ";
    }
    cout << "\n ----------- \n";*/
    assert(s[where2[where[level][i]]].count(trees[level].getmax(seg[where[level][i]].first, seg[where[level][i]].second)));
    s[where2[where[level][i]]].erase(s[where2[where[level][i]]].find(trees[level].getmax(seg[where[level][i]].first, seg[where[level][i]].second)));
    trees[level].add(l, r, delta);
    all[where[level][i]] = trees[level].getmax(seg[where[level][i]].first, seg[where[level][i]].second);
    s[where2[where[level][i]]].insert(trees[level].getmax(seg[where[level][i]].first, seg[where[level][i]].second));

    {
      ll cur = 0;
      auto it = s[where2[where[level][i]]].end();
      it--;
      cur += *it;
      it--;
      cur += *it;
      tog.insert(cur);
    }

  }
}

void build_centroid(int a, int level) {
  build_sub(a);
  total_under = sub[a];
  a = fcen(a);
  blocked[a] = 1;

  kek2++;
  s.push_back({});

  for (int it = 1; it <= 2; it++) {
    kek++;
    all.push_back(0);
    seg.push_back({0, 0});
    s.back().insert(0);
    where2.push_back(kek2);
  }

  if (1) {
  ///  cout << "centroid at " << level << " : " << a << "\n";
  }

  for (auto &I : gindex[a]) {
    int b = sum_edge[I] - a;
    if (blocked[b]) {
      continue;
    }

    kek++;
    all.push_back(0);
    vrt[level][I] = b;
    where[level][I] = kek;
    prep(b, a, level);
    if (kek == 3) {
      assert((int) seg.size() == 3);
    ///  cout << " oooooooooooooooooooooooooo " << low[level][b] << " " << high[level][b] << "\n";
    }
    seg.push_back({low[level][b], high[level][b]});
    where2.push_back(kek2);
    s.back().insert(0);
  }

  for (auto &I : gindex[a]) {
    int b = sum_edge[I] - a;
    if (blocked[b]) {
      continue;
    }
    build_centroid(b, level + 1);
  }
}

ll get_diam() {
  ll sol = 0;
  for (auto &s2 : s) {
    assert((int) s2.size() >= 2);
    auto it = s2.end();
    ll cur = 0;
    it--;
    cur += *it;
    it--;
    cur += *it;
    sol = max(sol, cur);
  }
  return sol;
}

int xx[N], yy[N];

int main() {
  if (home == 0) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  } else {
    freopen ("input.txt", "r", stdin);
  }
  cin >> n >> q >> w;
  for (int i = 0; i < K; i++) {
    for (int j = 0; j < N; j++) {
      where[i][j] = -1;
    }
    trees[i].init(n);
  }
  for (int i = 1; i < n; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    xx[i] = a;
    yy[i] = b;
    sum_edge[i] = a + b;
    gindex[a].push_back(i);
    gindex[b].push_back(i);
    val_edge[i] = c;
  }
  build_centroid(1, 0);
  for (int i = 1; i < n; i++) {
    add(i, val_edge[i]);
  }
  ll last = 0;
  for (int iq = 1; iq <= q; iq++) {
    int d, e;
    cin >> d >> e;
    d = (d + last) % (n - 1) + 1;
    e = (e + last) % w;
    assert(1 <= d && d <= n - 1);
    add(d, -val_edge[d] + e);
    val_edge[d] = e;
    if (tog.empty()) {
      last = 0;
    } else {
      auto it = tog.end();
      it--;
      last = *it;
    }
    /*if (last == 5596) {
      cout << "done\n";
      for (int i = 1; i < n; i++) {
        cout << xx[i] << " " << yy[i] << " " << val_edge[i] << "\n";
      }
      exit(0);
    }*/

    cout << last << "\n";

  }
  return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:279:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  279 |     freopen ("input.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27