oj.uz

답안 #618885

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
618885 2022-08-02T08:11:12 Z juancarlovieri Dynamic Diameter (CEOI19_diameter) C++17
11 / 100
 5000 ms 18868 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3364 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 2 ms 3412 KB Output is correct
8 Correct 3 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 3412 KB Output is correct
12 Correct 3 ms 3412 KB Output is correct
13 Correct 3 ms 3412 KB Output is correct
14 Correct 3 ms 3412 KB Output is correct
15 Correct 3 ms 3412 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 3 ms 3412 KB Output is correct
18 Correct 4 ms 3412 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3364 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 2 ms 3412 KB Output is correct
8 Correct 3 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 3412 KB Output is correct
12 Correct 3 ms 3412 KB Output is correct
13 Correct 3 ms 3412 KB Output is correct
14 Correct 3 ms 3412 KB Output is correct
15 Correct 3 ms 3412 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 3 ms 3412 KB Output is correct
18 Correct 4 ms 3412 KB Output is correct
19 Correct 500 ms 3748 KB Output is correct
20 Correct 800 ms 3624 KB Output is correct
21 Correct 2426 ms 3636 KB Output is correct
22 Correct 4727 ms 3920 KB Output is correct
23 Correct 3041 ms 4372 KB Output is correct
24 Execution timed out 5072 ms 4256 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 6 ms 3476 KB Output is correct
4 Correct 47 ms 3476 KB Output is correct
5 Correct 205 ms 3848 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 4 ms 3416 KB Output is correct
8 Correct 5 ms 3540 KB Output is correct
9 Correct 30 ms 3540 KB Output is correct
10 Correct 308 ms 3704 KB Output is correct
11 Correct 1409 ms 3968 KB Output is correct
12 Correct 9 ms 4116 KB Output is correct
13 Correct 41 ms 4180 KB Output is correct
14 Correct 300 ms 4212 KB Output is correct
15 Correct 3200 ms 4312 KB Output is correct
16 Execution timed out 5036 ms 4360 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 3620 KB Output is correct
2 Correct 530 ms 3656 KB Output is correct
3 Correct 2511 ms 3788 KB Output is correct
4 Execution timed out 5089 ms 4136 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5095 ms 18868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3364 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 2 ms 3412 KB Output is correct
8 Correct 3 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 3412 KB Output is correct
12 Correct 3 ms 3412 KB Output is correct
13 Correct 3 ms 3412 KB Output is correct
14 Correct 3 ms 3412 KB Output is correct
15 Correct 3 ms 3412 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 3 ms 3412 KB Output is correct
18 Correct 4 ms 3412 KB Output is correct
19 Correct 500 ms 3748 KB Output is correct
20 Correct 800 ms 3624 KB Output is correct
21 Correct 2426 ms 3636 KB Output is correct
22 Correct 4727 ms 3920 KB Output is correct
23 Correct 3041 ms 4372 KB Output is correct
24 Execution timed out 5072 ms 4256 KB Time limit exceeded
25 Halted 0 ms 0 KB -