Submission #945417

#	Time	Username	Problem	Language	Result	Execution time	Memory
945417		dorjderem	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	5038 ms	16332 KiB

diameter

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

#define endl "\n"
#define ll long long

const int MOD = 1e9 + 7;
const int mx = 1e5 + 10;
unordered_map<ll, ll> cost[mx];
vector<ll> tree[mx];
ll ans = 0;

ll dfs(ll node, vector<bool> &vis) {
  vis[node] = 1;
  ll one = -1, second = -1;
  for (ll nex : tree[node]) {
    if (vis[nex] == 0) {
      ll val = cost[node][nex] + dfs(nex, vis);
      if (val >= one) {
        second = one;
        one = val;
      } else if (val > second) {
        second = val;
      }
    }
  }
  if (one == -1 && second == -1) {
    return 0;
  } else if (second == -1) {
    ans = max(ans, one);
  } else {
    ans = max(ans, one + second);
  }
  return one;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n, q, w;
  cin >> n >> q >> w;
  vector<pair<ll, ll>> arr(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    tree[a].push_back(b);
    tree[b].push_back(a);
    cost[a][b] = c;
    cost[b][a] = c;
    arr[i] = {a, b};
  }

  ll last = 0;
  while (q--) {
    ll d, e;
    cin >> d >> e;
    d = (d + last) % (n - 1);
    e = (e + last) % w;
    pair<ll, ll> c = arr[d];
    cost[c.first][c.second] = e;
    cost[c.second][c.first] = e;
    // dp method
    // build up from root nodes of tree
    vector<bool> vis(n + 1, 0);
    ans = 0;
    dfs(1, vis);
    last = ans;
    cout << ans << endl;
  }

  return 0;
}

// what if its star?
// does it make any difference?

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27