Submission #1005958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005958		vjudge1	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	5063 ms	20060 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using pil = pair<int, i64>;
using pli = pair<i64, int>;
const int N = 1e5 + 5;
#define ALL(a) a.begin(), a.end()
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 ans = 0;
i64 last = 0;
i64 maxw = 0;
vector<pli> best[N];

void DFS(int u, int p) {
    best[u].clear();

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

        DFS(v, u);
        best[u].emplace_back(best[v].front().first + w, v);
    }

    best[u].emplace_back(0, u);

    while(best[u].size() < 2)
        best[u].emplace_back(0, 0);

    sort(ALL(best[u]));
    reverse(ALL(best[u]));

    while(best[u].size() > 2)
        best[u].pop_back();
}

void GET(int u, int p, i64 cur) {
    ans = max(ans, best[u][0].first + best[u][1].first);
    ans = max(ans, cur + best[u][0].first);

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

        i64 b = max(cur, best[u].front().second == v ? best[u].back().first : best[u].front().first) + w;
        GET(v, u, b);
    }
}

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) {
//            cout << u << " " << v << " " << w << "\n";
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
        }

        ans = 0;
        DFS(1, 0);
        GET(1, 0, 0);
        cout << ans << "\n";

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

        last = ans;
    }
}

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