oj.uz

Submission #659930

# Submission time Handle Problem Language Result Execution time Memory
659930 2022-11-19T18:41:51 Z 600Mihnea Dynamic Diameter (CEOI19_diameter) C++17
24 / 100
 5000 ms 169528 KB 
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;

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];
   /* 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));
  }
}

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;
    last = get_diam();
    /*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

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 4 ms 10580 KB Output is correct
4 Correct 5 ms 10580 KB Output is correct
5 Correct 5 ms 10580 KB Output is correct
6 Correct 5 ms 10580 KB Output is correct
7 Correct 5 ms 10580 KB Output is correct
8 Correct 5 ms 10708 KB Output is correct
9 Correct 5 ms 10628 KB Output is correct
10 Correct 5 ms 10708 KB Output is correct
11 Correct 5 ms 10616 KB Output is correct
12 Correct 5 ms 10632 KB Output is correct
13 Correct 5 ms 10760 KB Output is correct
14 Correct 7 ms 10708 KB Output is correct
15 Correct 6 ms 10700 KB Output is correct
16 Correct 6 ms 10708 KB Output is correct
17 Correct 7 ms 10708 KB Output is correct
18 Correct 6 ms 10828 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 4 ms 10580 KB Output is correct
4 Correct 5 ms 10580 KB Output is correct
5 Correct 5 ms 10580 KB Output is correct
6 Correct 5 ms 10580 KB Output is correct
7 Correct 5 ms 10580 KB Output is correct
8 Correct 5 ms 10708 KB Output is correct
9 Correct 5 ms 10628 KB Output is correct
10 Correct 5 ms 10708 KB Output is correct
11 Correct 5 ms 10616 KB Output is correct
12 Correct 5 ms 10632 KB Output is correct
13 Correct 5 ms 10760 KB Output is correct
14 Correct 7 ms 10708 KB Output is correct
15 Correct 6 ms 10700 KB Output is correct
16 Correct 6 ms 10708 KB Output is correct
17 Correct 7 ms 10708 KB Output is correct
18 Correct 6 ms 10828 KB Output is correct
19 Correct 67 ms 12436 KB Output is correct
20 Correct 70 ms 12468 KB Output is correct
21 Correct 90 ms 12492 KB Output is correct
22 Correct 85 ms 12544 KB Output is correct
23 Correct 254 ms 19428 KB Output is correct
24 Correct 292 ms 19724 KB Output is correct
25 Correct 296 ms 19760 KB Output is correct
26 Correct 327 ms 20248 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10500 KB Output is correct
2 Correct 5 ms 10580 KB Output is correct
3 Correct 6 ms 10512 KB Output is correct
4 Correct 23 ms 10712 KB Output is correct
5 Correct 89 ms 11748 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 6 ms 11348 KB Output is correct
8 Correct 7 ms 11348 KB Output is correct
9 Correct 14 ms 11348 KB Output is correct
10 Correct 85 ms 11620 KB Output is correct
11 Correct 412 ms 12636 KB Output is correct
12 Correct 19 ms 18772 KB Output is correct
13 Correct 23 ms 18628 KB Output is correct
14 Correct 88 ms 18708 KB Output is correct
15 Correct 683 ms 18824 KB Output is correct
16 Correct 3622 ms 20212 KB Output is correct
17 Correct 299 ms 169336 KB Output is correct
18 Correct 419 ms 169312 KB Output is correct
19 Correct 1887 ms 169336 KB Output is correct
20 Execution timed out 5096 ms 169528 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12372 KB Output is correct
2 Correct 139 ms 12496 KB Output is correct
3 Correct 579 ms 13288 KB Output is correct
4 Correct 1140 ms 13848 KB Output is correct
5 Correct 207 ms 28288 KB Output is correct
6 Correct 973 ms 28524 KB Output is correct
7 Correct 4371 ms 29012 KB Output is correct
8 Execution timed out 5057 ms 29380 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5051 ms 139856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 4 ms 10580 KB Output is correct
4 Correct 5 ms 10580 KB Output is correct
5 Correct 5 ms 10580 KB Output is correct
6 Correct 5 ms 10580 KB Output is correct
7 Correct 5 ms 10580 KB Output is correct
8 Correct 5 ms 10708 KB Output is correct
9 Correct 5 ms 10628 KB Output is correct
10 Correct 5 ms 10708 KB Output is correct
11 Correct 5 ms 10616 KB Output is correct
12 Correct 5 ms 10632 KB Output is correct
13 Correct 5 ms 10760 KB Output is correct
14 Correct 7 ms 10708 KB Output is correct
15 Correct 6 ms 10700 KB Output is correct
16 Correct 6 ms 10708 KB Output is correct
17 Correct 7 ms 10708 KB Output is correct
18 Correct 6 ms 10828 KB Output is correct
19 Correct 67 ms 12436 KB Output is correct
20 Correct 70 ms 12468 KB Output is correct
21 Correct 90 ms 12492 KB Output is correct
22 Correct 85 ms 12544 KB Output is correct
23 Correct 254 ms 19428 KB Output is correct
24 Correct 292 ms 19724 KB Output is correct
25 Correct 296 ms 19760 KB Output is correct
26 Correct 327 ms 20248 KB Output is correct
27 Correct 5 ms 10500 KB Output is correct
28 Correct 5 ms 10580 KB Output is correct
29 Correct 6 ms 10512 KB Output is correct
30 Correct 23 ms 10712 KB Output is correct
31 Correct 89 ms 11748 KB Output is correct
32 Correct 5 ms 10452 KB Output is correct
33 Correct 6 ms 11348 KB Output is correct
34 Correct 7 ms 11348 KB Output is correct
35 Correct 14 ms 11348 KB Output is correct
36 Correct 85 ms 11620 KB Output is correct
37 Correct 412 ms 12636 KB Output is correct
38 Correct 19 ms 18772 KB Output is correct
39 Correct 23 ms 18628 KB Output is correct
40 Correct 88 ms 18708 KB Output is correct
41 Correct 683 ms 18824 KB Output is correct
42 Correct 3622 ms 20212 KB Output is correct
43 Correct 299 ms 169336 KB Output is correct
44 Correct 419 ms 169312 KB Output is correct
45 Correct 1887 ms 169336 KB Output is correct
46 Execution timed out 5096 ms 169528 KB Time limit exceeded
47 Halted 0 ms 0 KB -