oj.uz

Submission #618896

# Submission time Handle Problem Language Result Execution time Memory
618896 2022-08-02T08:15:06 Z juancarlovieri Dynamic Diameter (CEOI19_diameter) C++17
36 / 100
 5000 ms 26412 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];

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) {
  ++time;
  in[cur] = time;
  for (auto [i, w] : edge[cur]) {
    if (i == prev) continue;
    depth[i] = depth[cur] + w;
    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);
  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;  
    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;
    while(cur != -1) {
      old[cur] = getmaks(cur);
      all.insert(old[cur]);
      cur = par[cur];
    }
    // cout << maks << endl;
    // cout << maks + maks2 << endl;
    // last = getmaks(0);
    auto it = all.end();
    --it;
    last = (*it);
    // 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:91: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]
   91 |   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:121: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]
  121 |     for (int j = 0; j < edge[i].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~~~

Subtask #1
11.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 4 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 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 4 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 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 4 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 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 4 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 107 ms 3740 KB Output is correct
20 Correct 172 ms 3864 KB Output is correct
21 Correct 559 ms 3996 KB Output is correct
22 Correct 951 ms 3920 KB Output is correct
23 Correct 134 ms 4540 KB Output is correct
24 Correct 948 ms 4688 KB Output is correct
25 Correct 3444 ms 4604 KB Output is correct
26 Execution timed out 5043 ms 4852 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 2 ms 3412 KB Output is correct
3 Correct 9 ms 3536 KB Output is correct
4 Correct 73 ms 3572 KB Output is correct
5 Correct 359 ms 3872 KB Output is correct
6 Correct 2 ms 3448 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 84 ms 3672 KB Output is correct
11 Correct 403 ms 4056 KB Output is correct
12 Correct 7 ms 4372 KB Output is correct
13 Correct 9 ms 4388 KB Output is correct
14 Correct 17 ms 4372 KB Output is correct
15 Correct 101 ms 4492 KB Output is correct
16 Correct 492 ms 4872 KB Output is correct
17 Correct 113 ms 21840 KB Output is correct
18 Correct 112 ms 21836 KB Output is correct
19 Correct 127 ms 21924 KB Output is correct
20 Correct 233 ms 22028 KB Output is correct
21 Correct 627 ms 22424 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3668 KB Output is correct
2 Correct 87 ms 3900 KB Output is correct
3 Correct 387 ms 4012 KB Output is correct
4 Correct 790 ms 4384 KB Output is correct
5 Correct 30 ms 5512 KB Output is correct
6 Correct 129 ms 5568 KB Output is correct
7 Correct 574 ms 5796 KB Output is correct
8 Correct 1154 ms 6160 KB Output is correct
9 Correct 102 ms 14100 KB Output is correct
10 Correct 231 ms 14360 KB Output is correct
11 Correct 840 ms 15112 KB Output is correct
12 Correct 1619 ms 15780 KB Output is correct
13 Correct 209 ms 24972 KB Output is correct
14 Correct 356 ms 24936 KB Output is correct
15 Correct 1184 ms 25544 KB Output is correct
16 Correct 2162 ms 26412 KB Output is correct
17 Correct 3134 ms 26292 KB Output is correct

Subtask #5
0 / 24.0

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

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 4 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 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 4 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 107 ms 3740 KB Output is correct
20 Correct 172 ms 3864 KB Output is correct
21 Correct 559 ms 3996 KB Output is correct
22 Correct 951 ms 3920 KB Output is correct
23 Correct 134 ms 4540 KB Output is correct
24 Correct 948 ms 4688 KB Output is correct
25 Correct 3444 ms 4604 KB Output is correct
26 Execution timed out 5043 ms 4852 KB Time limit exceeded
27 Halted 0 ms 0 KB -