oj.uz

답안 #618930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
618930 2022-08-02T08:25:18 Z juancarlovieri Dynamic Diameter (CEOI19_diameter) C++17
42 / 100
 5000 ms 30788 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;
      // puts("TES");
    if (maksdepth < 20 and 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);
    if (n <= 5000) {
      last = 0;
      for (int i = 0; i < n; ++i) {
        // cout << getmaks(i) << endl;
        last = max(last, getmaks(i));
      }
      cout << last << endl;
      continue;
    }
    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

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

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3412 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 3540 KB Output is correct
8 Correct 5 ms 3540 KB Output is correct
9 Correct 5 ms 3540 KB Output is correct
10 Correct 4 ms 3540 KB Output is correct
11 Correct 7 ms 3540 KB Output is correct
12 Correct 5 ms 3540 KB Output is correct
13 Correct 6 ms 3540 KB Output is correct
14 Correct 5 ms 3540 KB Output is correct
15 Correct 6 ms 3540 KB Output is correct
16 Correct 6 ms 3540 KB Output is correct
17 Correct 6 ms 3540 KB Output is correct
18 Correct 7 ms 3540 KB Output is correct
19 Correct 1978 ms 3748 KB Output is correct
20 Correct 2241 ms 3732 KB Output is correct
21 Correct 2546 ms 3752 KB Output is correct
22 Correct 2997 ms 3788 KB Output is correct
23 Execution timed out 5043 ms 4540 KB Time limit exceeded
24 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 3528 KB Output is correct
4 Correct 71 ms 3584 KB Output is correct
5 Correct 301 ms 3844 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 14 ms 3616 KB Output is correct
10 Correct 116 ms 3668 KB Output is correct
11 Correct 550 ms 4044 KB Output is correct
12 Correct 10 ms 4348 KB Output is correct
13 Correct 12 ms 4496 KB Output is correct
14 Correct 17 ms 4468 KB Output is correct
15 Correct 105 ms 4488 KB Output is correct
16 Correct 473 ms 4824 KB Output is correct
17 Correct 112 ms 21804 KB Output is correct
18 Correct 115 ms 21852 KB Output is correct
19 Correct 129 ms 21920 KB Output is correct
20 Correct 221 ms 21928 KB Output is correct
21 Correct 594 ms 22512 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 401 ms 3736 KB Output is correct
2 Correct 4096 ms 3888 KB Output is correct
3 Execution timed out 5018 ms 3888 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 634 ms 24436 KB Output is correct
2 Correct 637 ms 24372 KB Output is correct
3 Correct 660 ms 24492 KB Output is correct
4 Correct 856 ms 24444 KB Output is correct
5 Correct 991 ms 24348 KB Output is correct
6 Correct 774 ms 23940 KB Output is correct
7 Correct 692 ms 27012 KB Output is correct
8 Correct 712 ms 26844 KB Output is correct
9 Correct 705 ms 26928 KB Output is correct
10 Correct 763 ms 26852 KB Output is correct
11 Correct 889 ms 26696 KB Output is correct
12 Correct 727 ms 25604 KB Output is correct
13 Correct 675 ms 30640 KB Output is correct
14 Correct 731 ms 30656 KB Output is correct
15 Correct 722 ms 30624 KB Output is correct
16 Correct 829 ms 30576 KB Output is correct
17 Correct 871 ms 29948 KB Output is correct
18 Correct 765 ms 26888 KB Output is correct
19 Correct 641 ms 30616 KB Output is correct
20 Correct 721 ms 30788 KB Output is correct
21 Correct 697 ms 30728 KB Output is correct
22 Correct 835 ms 30576 KB Output is correct
23 Correct 844 ms 29944 KB Output is correct
24 Correct 774 ms 27060 KB Output is correct

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3412 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 3540 KB Output is correct
8 Correct 5 ms 3540 KB Output is correct
9 Correct 5 ms 3540 KB Output is correct
10 Correct 4 ms 3540 KB Output is correct
11 Correct 7 ms 3540 KB Output is correct
12 Correct 5 ms 3540 KB Output is correct
13 Correct 6 ms 3540 KB Output is correct
14 Correct 5 ms 3540 KB Output is correct
15 Correct 6 ms 3540 KB Output is correct
16 Correct 6 ms 3540 KB Output is correct
17 Correct 6 ms 3540 KB Output is correct
18 Correct 7 ms 3540 KB Output is correct
19 Correct 1978 ms 3748 KB Output is correct
20 Correct 2241 ms 3732 KB Output is correct
21 Correct 2546 ms 3752 KB Output is correct
22 Correct 2997 ms 3788 KB Output is correct
23 Execution timed out 5043 ms 4540 KB Time limit exceeded
24 Halted 0 ms 0 KB -