Submission #618850

# Submission time Handle Problem Language Result Execution time Memory
618850 2022-08-02T07:55:49 Z juancarlovieri Dynamic Diameter (CEOI19_diameter) C++17
0 / 100
5000 ms 18880 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(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);
    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(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) {
      |                     ~~^~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 8 ms 3412 KB Output is correct
4 Correct 45 ms 3516 KB Output is correct
5 Correct 223 ms 3768 KB Output is correct
6 Correct 2 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 29 ms 3540 KB Output is correct
10 Correct 271 ms 3600 KB Output is correct
11 Correct 1417 ms 4204 KB Output is correct
12 Correct 9 ms 4116 KB Output is correct
13 Correct 43 ms 4212 KB Output is correct
14 Correct 320 ms 4220 KB Output is correct
15 Correct 2951 ms 4440 KB Output is correct
16 Execution timed out 5079 ms 4440 KB Time limit exceeded
17 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 3540 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 5095 ms 18880 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -