Submission #689342

#	Time	Username	Problem	Language	Result	Execution time	Memory
689342		600Mihnea	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	5037 ms	177628 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;
    tree.resize(4 * (n + 7), 0);
    lazy.resize(4 * (n + 7), 0);
  }

  void add(int v, int tl, int tr, int l, int r, ll x) {
    if (tr < l || r < tl) {
      return;
    }
    if (l <= tl && tr <= r) {
      tree[v] += x;
      lazy[v] += x;
      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]) + lazy[v];
  }

  ll getmax(int v, int tl, int tr, int l, int r) {
    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)) + lazy[v];
  }

  void add(int l, int r, ll x) {
    add(1, 1, n, l, r, x);
  }

  ll getmax(int l, int r) {
    return getmax(1, 1, n, l, r);;
  }
};

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);
    }
  }
}

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];
  }
  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;
      if ((int)s[where2[where[level][i]]].size() == 0) {}
      else
        if ((int)s[where2[where[level][i]]].size() == 1) {
          cur = *s[where2[where[level][i]]].begin();
        }
        else {
          auto it = s[where2[where[level][i]]].end();
          it--;
          cur += *it;
          it--;
          cur += *it;
        }
      if (tog.count(cur)) {
        tog.erase(tog.find(cur));
      }
    }
    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;
      if ((int)s[where2[where[level][i]]].size() == 0) {}
      else
        if ((int)s[where2[where[level][i]]].size() == 1) {
          cur = *s[where2[where[level][i]]].begin();
        }
        else {
          auto it = s[where2[where[level][i]]].end();
          it--;
          cur += *it;
          it--;
          cur += *it;
        }
      tog.insert(cur);
    }

  }
}

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

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

  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);
    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) {
    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;
    add(d, -val_edge[d] + e);
    val_edge[d] = e;
    if (tog.empty()) {
      last = 0;
    }
    else {
      auto it = tog.end();
      it--;
      last = *it;
    }

    cout << last << "\n";

  }
  return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int fcen(int, int)':
diameter.cpp:102:1: warning: control reaches end of non-void function [-Wreturn-type]
  102 | }
      | ^
diameter.cpp: In function 'int main()':
diameter.cpp:247:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  247 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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