oj.uz

Submission #619298

# Submission time Handle Problem Language Result Execution time Memory
619298 2022-08-02T11:00:10 Z juancarlovieri Dynamic Diameter (CEOI19_diameter) C++17
73 / 100
 3213 ms 41448 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int long long
#define sm (ss + se) / 2
#define time mytime

void myassert(bool a) {
  while (!a);
}

int time = -1;
ll tree[400005];
ll pend[400004];
vector<pair<int, int>> edge[100005];
vector<pair<int, int>> edge2[100005];
int depth[100005];
int in[100005], out[100005];
int par[100005];
ll old[100005];
int maksdepth;

void push(int i, int ss, int se) {
  if (pend[i] != 0) {
    tree[i] += pend[i];
    if (ss != se) {
      pend[i * 2] += pend[i];
      pend[i * 2 + 1] += pend[i];
    }
    pend[i] = 0;
  }
}

void upd(int l, int r, int val, int ss = 0, int se  = 100000, int i = 1) {
  myassert(l <= r);
  push(i, ss, se);
  if (ss > se or r < ss or l > se) return;
  if (l <= ss and r >= se) {
    pend[i] += val;
    push(i, ss, se);
    return;
  }
  upd(l, r, val, ss, sm, i * 2);
  upd(l, r, val, sm + 1, se, i * 2 + 1);
  tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}

int get(int l, int r, int ss = 0, int se = 100000, int i = 1) {
  myassert(l <= r);
  push(i, ss, se);
  if (ss > se or ss > r or se < l) return 0;
  if (ss >= l and se <= r) {
    return tree[i];
  }
  return max(get(l, r, ss, sm, i * 2), get(l, r, sm + 1, se, i * 2 + 1));
}

// int get(int l, int r) {
//   int ans = 0;
//   for (int i = l; i <= r; ++i) ans = max(ans, tree[i]);
//   return ans;
// }

// void upd(int l, int r, int val) {
//   for (int i = l; i <= r; ++i) tree[i] += val;
// }

void rek(int cur, int prev = -1) {
  maksdepth = max(maksdepth, depth[cur]);
  ++time;
  in[cur] = time;
  for (auto [i, w] : edge[cur]) {
    if (i == prev) continue;
    depth[i] = depth[cur] + 1;
    par[i] = cur;
    rek(i, cur);
  }
  out[cur] = time;
}

int getmaks(int i) {
  if (edge[i].empty()) return 0;
  int lo = 0, hi = edge[i].size();
  int maks = get(in[i], out[i]);
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (get(in[i], out[edge[i][mid].first]) == maks) {
      hi = mid - 1;
    } else lo = mid + 1;
  }
  int maks2 = 0;
  if (lo) maks2 = max(maks2, get(in[i], out[edge[i][lo - 1].first]));
  if (lo + 1 < edge[i].size()) maks2 = max(maks2, get(in[edge[i][lo + 1].first], out[i]));
  // cout << maks << ' ' << maks2 << get(in[i], in[i]) << ' ' << endl;

  // cout << maks + maks2 - get(in[i], in[i]) - get(in[i], in[i]) << endl;
  int par = get(in[i], in[i]);
  return maks - par + maks2 - (maks2 ? par : 0);
}

pair<int, int> find(int cur, int prev = -1) {
  pair<int, int> res = {0, cur};
  for (auto [i, w] : edge2[cur]) {
    if (i == prev) continue;
    auto tmp = find(i, cur);
    tmp.first += w;
    res = max(res, tmp);
  }
  return res;
}

signed main() {
  int n, q, w;
  cin >> n >> q >> w;
  vector<pair<pair<int, int>, int>> edges;
  for (int i = 0; i < n - 1; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    edge[u].push_back({v, w});
    edge[v].push_back({u, w});
    edge2[u].push_back({v, w});
    edge2[v].push_back({u, w});
    edges.push_back({{u, v}, w});
  }
  memset(par, -1, sizeof par);
  rek(0);
  // cout << maksdepth << endl;
  for (int i = 0; i < n; ++i) {
    // cout << depth[i] << ' ';
    // upd(in[i], out[i], depth[i]);
    for (auto [j, w] : edge[i]) {
      if (in[j] < in[i]) continue;
      // cout << in[j] << ' ' << out[j] << ' ' << w << endl;
      upd(in[j], out[j], w);
    }
    for (int j = 0; j < edge[i].size(); ++j) {
      if (edge[i][j].first == par[i]) {
        // cout << i << ' ' << par[i] << endl;
        edge[i].erase(edge[i].begin() + j);
        break;
      }
    }
  }
  // cout << in[2] << ' ' << out[2] << endl;
  // cout << getmaks(2) << endl;
  // return 0;
  multiset<int> all;
  for (int i = 0; i < n; ++i) {
    // cout << getmaks(i) << ' ';
    old[i] = getmaks(i);
    all.insert(old[i]);
  }
  // cout << endl;
  // return 0;
  int last = 0;
  // cout << get(3, 3) << endl;
  while (q--) {
    int d, e;
    cin >> d >> e;
    d = (d + last) % (n - 1);
    e = (e + last) % w;
    // cout << "REal " << d << ' ' << e << endl;

    auto prev = edges[d];
    edges[d].second = e;
    auto [u, v] = prev.first;
    if (in[u] > in[v]) swap(u, v);
    if (n <= 5000) {
      for (auto& [i, w] : edge2[u]) {
        if (i == v) w = e;
      }
      for (auto& [i, w] : edge2[v]) {
        if (i == u) w = e;
      }

      int tmp = find(0).second;
      // cout << find(0).first << endl;
      last = find(tmp).first;
      cout << last << endl; 
      // cout << find(tmp).first << endl;
      continue;
    }
    int cur = u;
    // for (auto i : all) cout << i << ' ';
    // cout << endl;
    // puts("TES");
    if (maksdepth < 20 and n >= 5000) {
      while (cur != -1) {
        // cout << getmaks(cur) << endl;
        all.erase(all.find(old[cur]));
        cur = par[cur];
      }
    }
    // cout << in[v] << ' ' << out[v] << ' ' << e - prev.second << endl;
    upd(in[v], out[v], e - prev.second);
    if (n <= 5000) {
      last = 0;
      for (int i = 0; i < n; ++i) {
        // cout << getmaks(i) << endl;
        last = max(last, getmaks(i));
      }
      cout << last << endl;
      continue;
    }
    cur = u;
    if (maksdepth < 20 or n <= 5000) {
      while (cur != -1) {
        old[cur] = getmaks(cur);
        all.insert(old[cur]);
        cur = par[cur];
      }
    }
    // cout << maks << endl;
    // cout << maks + maks2 << endl;
    // last = getmaks(0);
    if (maksdepth < 20 or n <= 5000) {
      auto it = all.end();
      --it;
      last = (*it);
    } else {
      last = getmaks(0);
    }
    // last = 0;
    // for (int i = 0; i < n; ++i) last = max(last, getmaks(i));
    cout << last << endl;
  }
}

Compilation message

diameter.cpp: In function 'long long int getmaks(long long int)':
diameter.cpp:94:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   if (lo + 1 < edge[i].size()) maks2 = max(maks2, get(in[edge[i][lo + 1].first], out[i]));
      |       ~~~~~~~^~~~~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:138:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for (int j = 0; j < edge[i].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5844 KB Output is correct
2 Correct 4 ms 5844 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 4 ms 5844 KB Output is correct
5 Correct 5 ms 5844 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 4 ms 5844 KB Output is correct
8 Correct 4 ms 5844 KB Output is correct
9 Correct 4 ms 5844 KB Output is correct
10 Correct 5 ms 5844 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5844 KB Output is correct
13 Correct 4 ms 5844 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 5 ms 5844 KB Output is correct
16 Correct 5 ms 5844 KB Output is correct
17 Correct 4 ms 5844 KB Output is correct
18 Correct 4 ms 5844 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5844 KB Output is correct
2 Correct 4 ms 5844 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 4 ms 5844 KB Output is correct
5 Correct 5 ms 5844 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 4 ms 5844 KB Output is correct
8 Correct 4 ms 5844 KB Output is correct
9 Correct 4 ms 5844 KB Output is correct
10 Correct 5 ms 5844 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5844 KB Output is correct
13 Correct 4 ms 5844 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 5 ms 5844 KB Output is correct
16 Correct 5 ms 5844 KB Output is correct
17 Correct 4 ms 5844 KB Output is correct
18 Correct 4 ms 5844 KB Output is correct
19 Correct 141 ms 6152 KB Output is correct
20 Correct 118 ms 6140 KB Output is correct
21 Correct 145 ms 6176 KB Output is correct
22 Correct 197 ms 6344 KB Output is correct
23 Correct 1086 ms 7156 KB Output is correct
24 Correct 1257 ms 7184 KB Output is correct
25 Correct 1292 ms 7360 KB Output is correct
26 Correct 1520 ms 7524 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5844 KB Output is correct
3 Correct 7 ms 5844 KB Output is correct
4 Correct 60 ms 5912 KB Output is correct
5 Correct 198 ms 6192 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 5 ms 5972 KB Output is correct
9 Correct 18 ms 5972 KB Output is correct
10 Correct 147 ms 6052 KB Output is correct
11 Correct 692 ms 6552 KB Output is correct
12 Correct 14 ms 6996 KB Output is correct
13 Correct 12 ms 6996 KB Output is correct
14 Correct 34 ms 6928 KB Output is correct
15 Correct 126 ms 7052 KB Output is correct
16 Correct 559 ms 7524 KB Output is correct
17 Correct 135 ms 28892 KB Output is correct
18 Correct 128 ms 28896 KB Output is correct
19 Correct 135 ms 28884 KB Output is correct
20 Correct 233 ms 29012 KB Output is correct
21 Correct 607 ms 29532 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6152 KB Output is correct
2 Correct 176 ms 6180 KB Output is correct
3 Correct 921 ms 6372 KB Output is correct
4 Correct 1717 ms 6872 KB Output is correct
5 Correct 34 ms 8328 KB Output is correct
6 Correct 131 ms 8464 KB Output is correct
7 Correct 570 ms 8704 KB Output is correct
8 Correct 1160 ms 9024 KB Output is correct
9 Correct 114 ms 18436 KB Output is correct
10 Correct 239 ms 18440 KB Output is correct
11 Correct 885 ms 18932 KB Output is correct
12 Correct 1631 ms 19008 KB Output is correct
13 Correct 236 ms 31024 KB Output is correct
14 Correct 360 ms 31128 KB Output is correct
15 Correct 1008 ms 31296 KB Output is correct
16 Correct 1848 ms 31660 KB Output is correct
17 Correct 3213 ms 31700 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 32052 KB Output is correct
2 Correct 734 ms 31996 KB Output is correct
3 Correct 710 ms 32120 KB Output is correct
4 Correct 926 ms 32144 KB Output is correct
5 Correct 980 ms 31668 KB Output is correct
6 Correct 777 ms 31232 KB Output is correct
7 Correct 757 ms 34580 KB Output is correct
8 Correct 706 ms 34548 KB Output is correct
9 Correct 807 ms 34588 KB Output is correct
10 Correct 950 ms 34516 KB Output is correct
11 Correct 1061 ms 34176 KB Output is correct
12 Correct 965 ms 32792 KB Output is correct
13 Correct 741 ms 37888 KB Output is correct
14 Correct 1053 ms 37804 KB Output is correct
15 Correct 1109 ms 37824 KB Output is correct
16 Correct 959 ms 37816 KB Output is correct
17 Correct 970 ms 37160 KB Output is correct
18 Correct 888 ms 34096 KB Output is correct
19 Correct 716 ms 37876 KB Output is correct
20 Correct 715 ms 37828 KB Output is correct
21 Correct 816 ms 41448 KB Output is correct
22 Correct 858 ms 41408 KB Output is correct
23 Correct 902 ms 40752 KB Output is correct
24 Correct 786 ms 37744 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5844 KB Output is correct
2 Correct 4 ms 5844 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 4 ms 5844 KB Output is correct
5 Correct 5 ms 5844 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 4 ms 5844 KB Output is correct
8 Correct 4 ms 5844 KB Output is correct
9 Correct 4 ms 5844 KB Output is correct
10 Correct 5 ms 5844 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5844 KB Output is correct
13 Correct 4 ms 5844 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 5 ms 5844 KB Output is correct
16 Correct 5 ms 5844 KB Output is correct
17 Correct 4 ms 5844 KB Output is correct
18 Correct 4 ms 5844 KB Output is correct
19 Correct 141 ms 6152 KB Output is correct
20 Correct 118 ms 6140 KB Output is correct
21 Correct 145 ms 6176 KB Output is correct
22 Correct 197 ms 6344 KB Output is correct
23 Correct 1086 ms 7156 KB Output is correct
24 Correct 1257 ms 7184 KB Output is correct
25 Correct 1292 ms 7360 KB Output is correct
26 Correct 1520 ms 7524 KB Output is correct
27 Correct 3 ms 5844 KB Output is correct
28 Correct 3 ms 5844 KB Output is correct
29 Correct 7 ms 5844 KB Output is correct
30 Correct 60 ms 5912 KB Output is correct
31 Correct 198 ms 6192 KB Output is correct
32 Correct 3 ms 5844 KB Output is correct
33 Correct 4 ms 5972 KB Output is correct
34 Correct 5 ms 5972 KB Output is correct
35 Correct 18 ms 5972 KB Output is correct
36 Correct 147 ms 6052 KB Output is correct
37 Correct 692 ms 6552 KB Output is correct
38 Correct 14 ms 6996 KB Output is correct
39 Correct 12 ms 6996 KB Output is correct
40 Correct 34 ms 6928 KB Output is correct
41 Correct 126 ms 7052 KB Output is correct
42 Correct 559 ms 7524 KB Output is correct
43 Correct 135 ms 28892 KB Output is correct
44 Correct 128 ms 28896 KB Output is correct
45 Correct 135 ms 28884 KB Output is correct
46 Correct 233 ms 29012 KB Output is correct
47 Correct 607 ms 29532 KB Output is correct
48 Correct 23 ms 6152 KB Output is correct
49 Correct 176 ms 6180 KB Output is correct
50 Correct 921 ms 6372 KB Output is correct
51 Correct 1717 ms 6872 KB Output is correct
52 Correct 34 ms 8328 KB Output is correct
53 Correct 131 ms 8464 KB Output is correct
54 Correct 570 ms 8704 KB Output is correct
55 Correct 1160 ms 9024 KB Output is correct
56 Correct 114 ms 18436 KB Output is correct
57 Correct 239 ms 18440 KB Output is correct
58 Correct 885 ms 18932 KB Output is correct
59 Correct 1631 ms 19008 KB Output is correct
60 Correct 236 ms 31024 KB Output is correct
61 Correct 360 ms 31128 KB Output is correct
62 Correct 1008 ms 31296 KB Output is correct
63 Correct 1848 ms 31660 KB Output is correct
64 Correct 3213 ms 31700 KB Output is correct
65 Correct 605 ms 32052 KB Output is correct
66 Correct 734 ms 31996 KB Output is correct
67 Correct 710 ms 32120 KB Output is correct
68 Correct 926 ms 32144 KB Output is correct
69 Correct 980 ms 31668 KB Output is correct
70 Correct 777 ms 31232 KB Output is correct
71 Correct 757 ms 34580 KB Output is correct
72 Correct 706 ms 34548 KB Output is correct
73 Correct 807 ms 34588 KB Output is correct
74 Correct 950 ms 34516 KB Output is correct
75 Correct 1061 ms 34176 KB Output is correct
76 Correct 965 ms 32792 KB Output is correct
77 Correct 741 ms 37888 KB Output is correct
78 Correct 1053 ms 37804 KB Output is correct
79 Correct 1109 ms 37824 KB Output is correct
80 Correct 959 ms 37816 KB Output is correct
81 Correct 970 ms 37160 KB Output is correct
82 Correct 888 ms 34096 KB Output is correct
83 Correct 716 ms 37876 KB Output is correct
84 Correct 715 ms 37828 KB Output is correct
85 Correct 816 ms 41448 KB Output is correct
86 Correct 858 ms 41408 KB Output is correct
87 Correct 902 ms 40752 KB Output is correct
88 Correct 786 ms 37744 KB Output is correct
89 Incorrect 613 ms 35160 KB Output isn't correct
90 Halted 0 ms 0 KB -