oj.uz

Submission #618887

# Submission time Handle Problem Language Result Execution time Memory
618887 2022-08-02T08:11:41 Z juancarlovieri Dynamic Diameter (CEOI19_diameter) C++17
11 / 100
 5000 ms 18804 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

int time = -1;
int tree[400005];
int pend[400004];
vector<pair<int, int>> edge[100005];
int depth[100005];
int in[100005], out[100005];
int par[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;
  return maks - get(in[i], in[i]) + maks2 - (maks2 ? get(in[i], in[i]) : 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) << ' ';
    all.insert(getmaks(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(getmaks(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) {
      all.insert(getmaks(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:89: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]
   89 |   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:118: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]
  118 |     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 3 ms 3420 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 3 ms 3412 KB Output is correct
7 Correct 3 ms 3412 KB Output is correct
8 Correct 4 ms 3412 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3420 KB Output is correct
12 Correct 4 ms 3412 KB Output is correct
13 Correct 4 ms 3456 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 4 ms 3412 KB Output is correct
16 Correct 4 ms 3412 KB Output is correct
17 Correct 5 ms 3412 KB Output is correct
18 Correct 4 ms 3412 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 3 ms 3420 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 3 ms 3412 KB Output is correct
7 Correct 3 ms 3412 KB Output is correct
8 Correct 4 ms 3412 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3420 KB Output is correct
12 Correct 4 ms 3412 KB Output is correct
13 Correct 4 ms 3456 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 4 ms 3412 KB Output is correct
16 Correct 4 ms 3412 KB Output is correct
17 Correct 5 ms 3412 KB Output is correct
18 Correct 4 ms 3412 KB Output is correct
19 Correct 319 ms 3620 KB Output is correct
20 Correct 467 ms 3616 KB Output is correct
21 Correct 1434 ms 3752 KB Output is correct
22 Correct 2297 ms 3676 KB Output is correct
23 Correct 1492 ms 4376 KB Output is correct
24 Execution timed out 5092 ms 4252 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #3
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 6 ms 3412 KB Output is correct
4 Correct 42 ms 3532 KB Output is correct
5 Correct 209 ms 3804 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3540 KB Output is correct
8 Correct 5 ms 3412 KB Output is correct
9 Correct 19 ms 3540 KB Output is correct
10 Correct 178 ms 3548 KB Output is correct
11 Correct 984 ms 3948 KB Output is correct
12 Correct 8 ms 4116 KB Output is correct
13 Correct 25 ms 4224 KB Output is correct
14 Correct 185 ms 4344 KB Output is correct
15 Correct 1780 ms 4220 KB Output is correct
16 Execution timed out 5098 ms 4484 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3624 KB Output is correct
2 Correct 149 ms 3652 KB Output is correct
3 Correct 716 ms 3828 KB Output is correct
4 Correct 1361 ms 4060 KB Output is correct
5 Correct 131 ms 5024 KB Output is correct
6 Correct 1311 ms 5320 KB Output is correct
7 Execution timed out 5082 ms 5220 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5052 ms 18804 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 3 ms 3420 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 3 ms 3412 KB Output is correct
7 Correct 3 ms 3412 KB Output is correct
8 Correct 4 ms 3412 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3420 KB Output is correct
12 Correct 4 ms 3412 KB Output is correct
13 Correct 4 ms 3456 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 4 ms 3412 KB Output is correct
16 Correct 4 ms 3412 KB Output is correct
17 Correct 5 ms 3412 KB Output is correct
18 Correct 4 ms 3412 KB Output is correct
19 Correct 319 ms 3620 KB Output is correct
20 Correct 467 ms 3616 KB Output is correct
21 Correct 1434 ms 3752 KB Output is correct
22 Correct 2297 ms 3676 KB Output is correct
23 Correct 1492 ms 4376 KB Output is correct
24 Execution timed out 5092 ms 4252 KB Time limit exceeded
25 Halted 0 ms 0 KB -