oj.uz

답안 #618815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
618815 2022-08-02T07:39:20 Z juancarlovieri Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 918 ms 29868 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(out[edge[i][lo + 1].first], out[i]));
  return maks - get(in[i], in[i]) + maks2 - get(in[i], in[i]);
}

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]) {
        edge[i].erase(edge[i].begin() + j);
        break;
      }
    }
  }
  multiset<int> all;
  for (int i = 0; i < n; ++i) {
    all.insert(getmaks(i));
  }
  // cout << endl;
  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);
    // cout << in[v] << ' ' << out[v] << ' ' << e - prev.second << endl;
    upd(in[v], out[v], e - prev.second);
    // cout << maks << endl;
    // cout << maks + maks2 << endl;
    last = getmaks(0);
    cout << last << endl;    
  }
}

Compilation message

diameter.cpp: In function 'long long int getmaks(long long int)':
diameter.cpp:90: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]
   90 |   if (lo + 1 < edge[i].size()) maks2 = max(maks2, get(out[edge[i][lo + 1].first], out[i]));
      |       ~~~~~~~^~~~~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:116: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]
  116 |     for (int j = 0; j < edge[i].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 3 ms 3412 KB Output is correct
3 Correct 8 ms 3520 KB Output is correct
4 Correct 83 ms 3524 KB Output is correct
5 Correct 321 ms 3940 KB Output is correct
6 Correct 3 ms 3412 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 4 ms 3540 KB Output is correct
9 Correct 12 ms 3540 KB Output is correct
10 Correct 80 ms 3624 KB Output is correct
11 Correct 376 ms 4052 KB Output is correct
12 Correct 7 ms 4372 KB Output is correct
13 Correct 9 ms 4372 KB Output is correct
14 Correct 15 ms 4372 KB Output is correct
15 Correct 115 ms 4516 KB Output is correct
16 Correct 462 ms 4912 KB Output is correct
17 Correct 114 ms 21032 KB Output is correct
18 Correct 115 ms 21032 KB Output is correct
19 Correct 128 ms 21208 KB Output is correct
20 Correct 227 ms 21236 KB Output is correct
21 Correct 600 ms 21708 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 3668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 611 ms 23608 KB Output is correct
2 Correct 656 ms 23672 KB Output is correct
3 Correct 635 ms 23660 KB Output is correct
4 Correct 776 ms 23752 KB Output is correct
5 Correct 857 ms 23624 KB Output is correct
6 Correct 773 ms 23088 KB Output is correct
7 Correct 668 ms 26188 KB Output is correct
8 Correct 765 ms 26188 KB Output is correct
9 Correct 787 ms 26036 KB Output is correct
10 Correct 782 ms 26224 KB Output is correct
11 Correct 839 ms 25820 KB Output is correct
12 Correct 761 ms 24844 KB Output is correct
13 Correct 698 ms 29808 KB Output is correct
14 Correct 713 ms 29804 KB Output is correct
15 Correct 784 ms 29868 KB Output is correct
16 Correct 854 ms 29736 KB Output is correct
17 Correct 918 ms 29176 KB Output is correct
18 Correct 821 ms 26140 KB Output is correct
19 Correct 710 ms 29776 KB Output is correct
20 Correct 745 ms 29840 KB Output is correct
21 Correct 820 ms 29792 KB Output is correct
22 Correct 851 ms 29756 KB Output is correct
23 Correct 876 ms 29112 KB Output is correct
24 Correct 768 ms 26192 KB Output is correct

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -