답안 #618844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
618844	2022-08-02T07:53:26 Z	juancarlovieri	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	5000 ms	18832 KB

diameter

#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]));
  // 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);
    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(out[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
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
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	3412 KB	Output is correct
4	Correct	44 ms	3528 KB	Output is correct
5	Correct	196 ms	3880 KB	Output is correct
6	Correct	2 ms	3412 KB	Output is correct
7	Correct	2 ms	3412 KB	Output is correct
8	Correct	4 ms	3540 KB	Output is correct
9	Correct	20 ms	3548 KB	Output is correct
10	Correct	169 ms	3712 KB	Output is correct
11	Correct	850 ms	3888 KB	Output is correct
12	Correct	8 ms	4116 KB	Output is correct
13	Correct	29 ms	4164 KB	Output is correct
14	Correct	175 ms	4328 KB	Output is correct
15	Correct	1759 ms	4360 KB	Output is correct
16	Execution timed out	5088 ms	4500 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-