oj.uz

Submission #659931

# Submission time Handle Problem Language Result Execution time Memory
659931 2022-11-19T18:44:37 Z 600Mihnea Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 5000 ms 193540 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;

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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 5 ms 10580 KB Output is correct
3 Correct 5 ms 10568 KB Output is correct
4 Correct 5 ms 10580 KB Output is correct
5 Correct 5 ms 10580 KB Output is correct
6 Correct 7 ms 10588 KB Output is correct
7 Correct 6 ms 10708 KB Output is correct
8 Correct 5 ms 10708 KB Output is correct
9 Correct 5 ms 10708 KB Output is correct
10 Correct 5 ms 10708 KB Output is correct
11 Correct 5 ms 10708 KB Output is correct
12 Correct 6 ms 10724 KB Output is correct
13 Correct 6 ms 10708 KB Output is correct
14 Correct 6 ms 10708 KB Output is correct
15 Correct 6 ms 10816 KB Output is correct
16 Correct 6 ms 10720 KB Output is correct
17 Correct 9 ms 10708 KB Output is correct
18 Correct 6 ms 10708 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 5 ms 10580 KB Output is correct
3 Correct 5 ms 10568 KB Output is correct
4 Correct 5 ms 10580 KB Output is correct
5 Correct 5 ms 10580 KB Output is correct
6 Correct 7 ms 10588 KB Output is correct
7 Correct 6 ms 10708 KB Output is correct
8 Correct 5 ms 10708 KB Output is correct
9 Correct 5 ms 10708 KB Output is correct
10 Correct 5 ms 10708 KB Output is correct
11 Correct 5 ms 10708 KB Output is correct
12 Correct 6 ms 10724 KB Output is correct
13 Correct 6 ms 10708 KB Output is correct
14 Correct 6 ms 10708 KB Output is correct
15 Correct 6 ms 10816 KB Output is correct
16 Correct 6 ms 10720 KB Output is correct
17 Correct 9 ms 10708 KB Output is correct
18 Correct 6 ms 10708 KB Output is correct
19 Correct 40 ms 12372 KB Output is correct
20 Correct 46 ms 12440 KB Output is correct
21 Correct 57 ms 12464 KB Output is correct
22 Correct 65 ms 12500 KB Output is correct
23 Correct 112 ms 19496 KB Output is correct
24 Correct 127 ms 19596 KB Output is correct
25 Correct 148 ms 19668 KB Output is correct
26 Correct 223 ms 20088 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 5 ms 10580 KB Output is correct
3 Correct 6 ms 10580 KB Output is correct
4 Correct 22 ms 10676 KB Output is correct
5 Correct 81 ms 10964 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 6 ms 11376 KB Output is correct
8 Correct 6 ms 11348 KB Output is correct
9 Correct 8 ms 11348 KB Output is correct
10 Correct 33 ms 11444 KB Output is correct
11 Correct 127 ms 11736 KB Output is correct
12 Correct 18 ms 18576 KB Output is correct
13 Correct 16 ms 18576 KB Output is correct
14 Correct 18 ms 18576 KB Output is correct
15 Correct 45 ms 18576 KB Output is correct
16 Correct 168 ms 19020 KB Output is correct
17 Correct 302 ms 168040 KB Output is correct
18 Correct 306 ms 168032 KB Output is correct
19 Correct 284 ms 168080 KB Output is correct
20 Correct 391 ms 168172 KB Output is correct
21 Correct 648 ms 170908 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12428 KB Output is correct
2 Correct 63 ms 12464 KB Output is correct
3 Correct 262 ms 12588 KB Output is correct
4 Correct 544 ms 12948 KB Output is correct
5 Correct 161 ms 28364 KB Output is correct
6 Correct 253 ms 28388 KB Output is correct
7 Correct 627 ms 28652 KB Output is correct
8 Correct 1169 ms 29180 KB Output is correct
9 Correct 969 ms 100624 KB Output is correct
10 Correct 1092 ms 101072 KB Output is correct
11 Correct 1828 ms 101336 KB Output is correct
12 Correct 2664 ms 102280 KB Output is correct
13 Correct 2192 ms 191824 KB Output is correct
14 Correct 2451 ms 192192 KB Output is correct
15 Correct 3046 ms 192796 KB Output is correct
16 Correct 3959 ms 193540 KB Output is correct
17 Execution timed out 5066 ms 193100 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5061 ms 139456 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 5 ms 10580 KB Output is correct
3 Correct 5 ms 10568 KB Output is correct
4 Correct 5 ms 10580 KB Output is correct
5 Correct 5 ms 10580 KB Output is correct
6 Correct 7 ms 10588 KB Output is correct
7 Correct 6 ms 10708 KB Output is correct
8 Correct 5 ms 10708 KB Output is correct
9 Correct 5 ms 10708 KB Output is correct
10 Correct 5 ms 10708 KB Output is correct
11 Correct 5 ms 10708 KB Output is correct
12 Correct 6 ms 10724 KB Output is correct
13 Correct 6 ms 10708 KB Output is correct
14 Correct 6 ms 10708 KB Output is correct
15 Correct 6 ms 10816 KB Output is correct
16 Correct 6 ms 10720 KB Output is correct
17 Correct 9 ms 10708 KB Output is correct
18 Correct 6 ms 10708 KB Output is correct
19 Correct 40 ms 12372 KB Output is correct
20 Correct 46 ms 12440 KB Output is correct
21 Correct 57 ms 12464 KB Output is correct
22 Correct 65 ms 12500 KB Output is correct
23 Correct 112 ms 19496 KB Output is correct
24 Correct 127 ms 19596 KB Output is correct
25 Correct 148 ms 19668 KB Output is correct
26 Correct 223 ms 20088 KB Output is correct
27 Correct 5 ms 10580 KB Output is correct
28 Correct 5 ms 10580 KB Output is correct
29 Correct 6 ms 10580 KB Output is correct
30 Correct 22 ms 10676 KB Output is correct
31 Correct 81 ms 10964 KB Output is correct
32 Correct 5 ms 10452 KB Output is correct
33 Correct 6 ms 11376 KB Output is correct
34 Correct 6 ms 11348 KB Output is correct
35 Correct 8 ms 11348 KB Output is correct
36 Correct 33 ms 11444 KB Output is correct
37 Correct 127 ms 11736 KB Output is correct
38 Correct 18 ms 18576 KB Output is correct
39 Correct 16 ms 18576 KB Output is correct
40 Correct 18 ms 18576 KB Output is correct
41 Correct 45 ms 18576 KB Output is correct
42 Correct 168 ms 19020 KB Output is correct
43 Correct 302 ms 168040 KB Output is correct
44 Correct 306 ms 168032 KB Output is correct
45 Correct 284 ms 168080 KB Output is correct
46 Correct 391 ms 168172 KB Output is correct
47 Correct 648 ms 170908 KB Output is correct
48 Correct 17 ms 12428 KB Output is correct
49 Correct 63 ms 12464 KB Output is correct
50 Correct 262 ms 12588 KB Output is correct
51 Correct 544 ms 12948 KB Output is correct
52 Correct 161 ms 28364 KB Output is correct
53 Correct 253 ms 28388 KB Output is correct
54 Correct 627 ms 28652 KB Output is correct
55 Correct 1169 ms 29180 KB Output is correct
56 Correct 969 ms 100624 KB Output is correct
57 Correct 1092 ms 101072 KB Output is correct
58 Correct 1828 ms 101336 KB Output is correct
59 Correct 2664 ms 102280 KB Output is correct
60 Correct 2192 ms 191824 KB Output is correct
61 Correct 2451 ms 192192 KB Output is correct
62 Correct 3046 ms 192796 KB Output is correct
63 Correct 3959 ms 193540 KB Output is correct
64 Execution timed out 5066 ms 193100 KB Time limit exceeded
65 Halted 0 ms 0 KB -