Submission #1245177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245177		Mousa_Aboubaker	Dynamic Diameter (CEOI19_diameter)	C++20	24 / 100	5093 ms	10400 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    long long w;
    cin >> n >> q >> w;
    vector<tuple<int, int, long long>> edges(n);
    for(int i = 1; i < n; i++)
    {
        auto &[u, v, c] = edges[i];
        cin >> u >> v >> c;
    }
    // how to find the diameter?
    // run two dfs
    auto find_diameter = [&]() -> long long
    {
        vector adj(n + 1, vector<pair<int, long long>>());
        for (int i = 1; i < n; i++)
        {
            auto [u, v, c] = edges[i];
            adj[u].push_back({v, c});
            adj[v].push_back({u, c});
        }
        vector<long long> dis(n + 1, 0);
        auto dfs = [&](auto self, int u, int p) -> void
        {
            for (auto [v, c] : adj[u])
            {
                if (v == p)
                    continue;
                dis[v] = dis[u] + c;
                self(self, v, u);
            }
        };
        dfs(dfs, 1, -1);
        int mx = max_element(dis.begin(), dis.end()) - dis.begin();
        dis[mx] = 0;
        dfs(dfs, mx, -1);
        mx = max_element(dis.begin(), dis.end()) - dis.begin();
        return dis[mx];
    };

    long long lst =0;
    while(q--)
    {
        int d;
        long long e;
        cin >> d >> e;
        d = (d + lst) % (n - 1) + 1;
        e = (e + lst) % w;
        auto &[u, v, c] = edges[d];
        c = e;
        long long res = find_diameter();
        cout << res << '\n';
        lst = res;
    }
}

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