Submission #1005913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005913		vjudge1	Dynamic Diameter (CEOI19_diameter)	C++17	11 / 100	5062 ms	11720 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using pil = pair<int, i64>;
const int N = 1e5 + 5;

struct edge {
    int u, v;
    i64 w;
    edge(int u = 0, int v = 0, i64 w = 0) : u(u), v(v), w(w) {}
};

int n;
int tc;
vector<pil> adj[N];
vector<edge> e;
i64 last = 0;
i64 maxw = 0;
i64 ans = 0;

void DFS(int u, int p, i64 cur) {
    ans = max(ans, cur);

    for(auto [v, w] : adj[u]) {
        if(v == p)
            continue;

        DFS(v, u, cur + w);
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> tc >> maxw;

    for(int i = 1; i < n; i++) {
        int u, v;
        i64 w;
        cin >> u >> v >> w;
        e.emplace_back(u, v, w);
    }

    while(tc--) {
        int p;
        i64 w;
        cin >> p >> w;
        p = (p + last) % (n - 1);
        w = (w + last) % maxw;
        e[p].w = w;

        for(auto [u, v, w] : e) {
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
        }

        ans = 0;

        for(int i = 1; i <= n; i++)
            DFS(i, 0, 0);

        cout << ans << "\n";

        for(int i = 1; i <= n; i++)
            adj[i].clear();

        last = ans;
    }
}

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