oj.uz

Submission #618913

# Submission time Handle Problem Language Result Execution time Memory
618913 2022-08-02T08:19:32 Z juancarlovieri Dynamic Diameter (CEOI19_diameter) C++17
49 / 100
 3102 ms 30664 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];
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);
}

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});
    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);
    int cur = u;
    // for (auto i : all) cout << i << ' ';
    // cout << endl;
    if (maksdepth < 20) {
      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);
    cur = u;
    if (maksdepth < 20) {
      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) {
      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:93: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]
   93 |   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:124: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]
  124 |     for (int j = 0; j < edge[i].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 3 ms 3540 KB Output is correct
9 Correct 3 ms 3540 KB Output is correct
10 Correct 2 ms 3540 KB Output is correct
11 Correct 4 ms 3540 KB Output is correct
12 Correct 3 ms 3540 KB Output is correct
13 Correct 3 ms 3540 KB Output is correct
14 Correct 3 ms 3540 KB Output is correct
15 Correct 3 ms 3540 KB Output is correct
16 Correct 3 ms 3540 KB Output is correct
17 Incorrect 3 ms 3540 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 3 ms 3540 KB Output is correct
9 Correct 3 ms 3540 KB Output is correct
10 Correct 2 ms 3540 KB Output is correct
11 Correct 4 ms 3540 KB Output is correct
12 Correct 3 ms 3540 KB Output is correct
13 Correct 3 ms 3540 KB Output is correct
14 Correct 3 ms 3540 KB Output is correct
15 Correct 3 ms 3540 KB Output is correct
16 Correct 3 ms 3540 KB Output is correct
17 Incorrect 3 ms 3540 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 8 ms 3412 KB Output is correct
4 Correct 68 ms 3696 KB Output is correct
5 Correct 304 ms 3812 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3540 KB Output is correct
8 Correct 3 ms 3540 KB Output is correct
9 Correct 10 ms 3540 KB Output is correct
10 Correct 89 ms 3668 KB Output is correct
11 Correct 448 ms 4080 KB Output is correct
12 Correct 7 ms 4372 KB Output is correct
13 Correct 9 ms 4436 KB Output is correct
14 Correct 19 ms 4372 KB Output is correct
15 Correct 109 ms 4492 KB Output is correct
16 Correct 546 ms 4992 KB Output is correct
17 Correct 119 ms 21908 KB Output is correct
18 Correct 127 ms 21964 KB Output is correct
19 Correct 125 ms 21928 KB Output is correct
20 Correct 214 ms 22008 KB Output is correct
21 Correct 623 ms 22608 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3668 KB Output is correct
2 Correct 76 ms 3892 KB Output is correct
3 Correct 390 ms 3996 KB Output is correct
4 Correct 854 ms 4216 KB Output is correct
5 Correct 30 ms 5552 KB Output is correct
6 Correct 148 ms 5576 KB Output is correct
7 Correct 627 ms 5920 KB Output is correct
8 Correct 1313 ms 6068 KB Output is correct
9 Correct 112 ms 13412 KB Output is correct
10 Correct 251 ms 13464 KB Output is correct
11 Correct 876 ms 13648 KB Output is correct
12 Correct 1700 ms 14012 KB Output is correct
13 Correct 197 ms 23168 KB Output is correct
14 Correct 434 ms 23328 KB Output is correct
15 Correct 995 ms 23584 KB Output is correct
16 Correct 1764 ms 24008 KB Output is correct
17 Correct 3102 ms 23996 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 24484 KB Output is correct
2 Correct 618 ms 24484 KB Output is correct
3 Correct 709 ms 24596 KB Output is correct
4 Correct 832 ms 24412 KB Output is correct
5 Correct 774 ms 24216 KB Output is correct
6 Correct 692 ms 23888 KB Output is correct
7 Correct 704 ms 26908 KB Output is correct
8 Correct 681 ms 26884 KB Output is correct
9 Correct 699 ms 26844 KB Output is correct
10 Correct 904 ms 26820 KB Output is correct
11 Correct 915 ms 26580 KB Output is correct
12 Correct 825 ms 25512 KB Output is correct
13 Correct 757 ms 30648 KB Output is correct
14 Correct 713 ms 30652 KB Output is correct
15 Correct 760 ms 30664 KB Output is correct
16 Correct 867 ms 30656 KB Output is correct
17 Correct 881 ms 30016 KB Output is correct
18 Correct 828 ms 26944 KB Output is correct
19 Correct 814 ms 30624 KB Output is correct
20 Correct 738 ms 30644 KB Output is correct
21 Correct 743 ms 30572 KB Output is correct
22 Correct 1004 ms 30584 KB Output is correct
23 Correct 974 ms 29980 KB Output is correct
24 Correct 923 ms 26940 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 3 ms 3540 KB Output is correct
9 Correct 3 ms 3540 KB Output is correct
10 Correct 2 ms 3540 KB Output is correct
11 Correct 4 ms 3540 KB Output is correct
12 Correct 3 ms 3540 KB Output is correct
13 Correct 3 ms 3540 KB Output is correct
14 Correct 3 ms 3540 KB Output is correct
15 Correct 3 ms 3540 KB Output is correct
16 Correct 3 ms 3540 KB Output is correct
17 Incorrect 3 ms 3540 KB Output isn't correct
18 Halted 0 ms 0 KB -