oj.uz

Submission #618917

# Submission time Handle Problem Language Result Execution time Memory
618917 2022-08-02T08:21:08 Z juancarlovieri Dynamic Diameter (CEOI19_diameter) C++17
60 / 100
 5000 ms 30684 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 or 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);
    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: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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 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 2 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 3 ms 3540 KB Output is correct
11 Correct 3 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 Correct 3 ms 3540 KB Output is correct
18 Correct 4 ms 3540 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 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 2 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 3 ms 3540 KB Output is correct
11 Correct 3 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 Correct 3 ms 3540 KB Output is correct
18 Correct 4 ms 3540 KB Output is correct
19 Correct 104 ms 3744 KB Output is correct
20 Correct 156 ms 3760 KB Output is correct
21 Correct 457 ms 3760 KB Output is correct
22 Correct 948 ms 3920 KB Output is correct
23 Correct 126 ms 4552 KB Output is correct
24 Correct 547 ms 4572 KB Output is correct
25 Correct 1723 ms 4732 KB Output is correct
26 Execution timed out 5093 ms 4848 KB Time limit exceeded
27 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 3 ms 3412 KB Output is correct
3 Correct 9 ms 3412 KB Output is correct
4 Correct 70 ms 3588 KB Output is correct
5 Correct 347 ms 3892 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 10 ms 3612 KB Output is correct
10 Correct 83 ms 3664 KB Output is correct
11 Correct 469 ms 4044 KB Output is correct
12 Correct 10 ms 4456 KB Output is correct
13 Correct 10 ms 4372 KB Output is correct
14 Correct 19 ms 4460 KB Output is correct
15 Correct 107 ms 4464 KB Output is correct
16 Correct 642 ms 4940 KB Output is correct
17 Correct 159 ms 21800 KB Output is correct
18 Correct 143 ms 21900 KB Output is correct
19 Correct 176 ms 21832 KB Output is correct
20 Correct 288 ms 21916 KB Output is correct
21 Correct 780 ms 22508 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3756 KB Output is correct
2 Correct 100 ms 3748 KB Output is correct
3 Correct 417 ms 4000 KB Output is correct
4 Correct 938 ms 4356 KB Output is correct
5 Correct 44 ms 5528 KB Output is correct
6 Correct 161 ms 5532 KB Output is correct
7 Correct 599 ms 5816 KB Output is correct
8 Correct 1232 ms 6104 KB Output is correct
9 Correct 116 ms 13396 KB Output is correct
10 Correct 265 ms 13388 KB Output is correct
11 Correct 889 ms 13656 KB Output is correct
12 Correct 1652 ms 13912 KB Output is correct
13 Correct 213 ms 23168 KB Output is correct
14 Correct 338 ms 23432 KB Output is correct
15 Correct 984 ms 23520 KB Output is correct
16 Correct 1751 ms 23804 KB Output is correct
17 Correct 3057 ms 23740 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 24448 KB Output is correct
2 Correct 634 ms 24488 KB Output is correct
3 Correct 612 ms 24440 KB Output is correct
4 Correct 767 ms 24488 KB Output is correct
5 Correct 785 ms 24284 KB Output is correct
6 Correct 743 ms 23924 KB Output is correct
7 Correct 605 ms 26972 KB Output is correct
8 Correct 657 ms 26924 KB Output is correct
9 Correct 733 ms 26924 KB Output is correct
10 Correct 802 ms 26976 KB Output is correct
11 Correct 836 ms 26672 KB Output is correct
12 Correct 740 ms 25484 KB Output is correct
13 Correct 683 ms 30652 KB Output is correct
14 Correct 690 ms 30572 KB Output is correct
15 Correct 740 ms 30684 KB Output is correct
16 Correct 819 ms 30572 KB Output is correct
17 Correct 990 ms 29940 KB Output is correct
18 Correct 860 ms 26988 KB Output is correct
19 Correct 785 ms 30588 KB Output is correct
20 Correct 825 ms 30600 KB Output is correct
21 Correct 790 ms 30604 KB Output is correct
22 Correct 833 ms 30516 KB Output is correct
23 Correct 890 ms 29888 KB Output is correct
24 Correct 744 ms 26964 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 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 2 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 3 ms 3540 KB Output is correct
11 Correct 3 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 Correct 3 ms 3540 KB Output is correct
18 Correct 4 ms 3540 KB Output is correct
19 Correct 104 ms 3744 KB Output is correct
20 Correct 156 ms 3760 KB Output is correct
21 Correct 457 ms 3760 KB Output is correct
22 Correct 948 ms 3920 KB Output is correct
23 Correct 126 ms 4552 KB Output is correct
24 Correct 547 ms 4572 KB Output is correct
25 Correct 1723 ms 4732 KB Output is correct
26 Execution timed out 5093 ms 4848 KB Time limit exceeded
27 Halted 0 ms 0 KB -