Submission #618815

#	Time	Username	Problem	Language	Result	Execution time	Memory
618815		juancarlovieri	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	918 ms	29868 KiB

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]));
  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 (stderr)

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