Submission #446249

#	Time	Username	Problem	Language	Result	Execution time	Memory
446249		benedict0724	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	5042 ms	59668 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

int cost[5002][5002], dist[5002];
vector<int> adj[5002];
pair<int, int> E[5002];
const int INF = 1e9;

void dfs(int x, int p = -1)
{
    for(int i : adj[x])
    {
        if(i == p) continue;
        dist[i] = dist[x] + cost[x][i];
        dfs(i, x);
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n, q, w; cin >> n >> q >> w;
    for(int i=0;i<n-1;i++)
    {
        int s, e, c; cin >> s >> e >> c;
        E[i] = {s, e};
        adj[s].push_back(e);
        adj[e].push_back(s);
        cost[s][e] = cost[e][s] = c;
    }

    int last = 0;
    for(int i=1;i<=q;i++)
    {
        int d, e;
        cin >> d >> e;
        d = (d + last)%(n-1);
        e = (e + last)%w;
        int a = E[d].first, b = E[d].second;
        cost[a][b] = cost[b][a] = e;

        dist[1] = 0;
        dfs(1);
        int next = 1;
        for(int i=1;i<=n;i++) if(dist[next] < dist[i]) next = i;
        dist[next] = 0;
        dfs(next);
        int ans = 0;
        for(int i=1;i<=n;i++) ans = max(ans, dist[i]);
        cout << ans << "\n";
        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