제출 #618913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
618913		juancarlovieri	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	3102 ms	30664 KiB

diameter

#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;
    if (maksdepth < 20) {
      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);
    cur = u;
    if (maksdepth < 20) {
      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) {
      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;
  }
}

컴파일 시 표준 에러 (stderr) 메시지

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: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 0 / 27