Submission #1245179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245179		Mousa_Aboubaker	Dynamic Diameter (CEOI19_diameter)	C++20	18 / 100	79 ms	18248 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);
    vector<long long> seg(n * 4);
    vector<long long> mx(n * 4);
    for (int i = 1; i < n; i++)
    {
        auto &[u, v, c] = edges[i];
        cin >> u >> v >> c;
    }
    vector adj(n + 1, vector<pair<int, long long>>());
    vector<pair<long long, long long>> ee(n, make_pair(0, 0));
    for (int i = 1; i < n; i++)
    {
        auto &[u, v, c] = edges[i];
        if (u > v)
            swap(u, v);
        if (v == u * 2)
            ee[u].first = c;
        else
            ee[u].second = c;
    }
    for (int i = n - 1; i >= 0; i--)
    {
        int v = i;
        seg[v] = max(seg[v * 2] + ee[v].first, seg[v * 2 + 1] + ee[v].second);
        mx[v] = max({mx[v * 2], mx[v * 2 + 1], seg[v * 2] + ee[v].first + seg[v * 2 + 1] + ee[v].second});
    }
    // 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;
    multiset<long long> st;
    for (int i = 1; i < n; i++)
    {
        auto &[u, v, c] = edges[i];
        st.insert(c);
    }
    while (q--)
    {
        int d;
        long long e;
        cin >> d >> e;
        d = (d + lst) % (n - 1) + 1;
        e = (e + lst) % w;
        auto &[u, vv, c] = edges[d];
        c = e;
        if (vv == u * 2)
            ee[u].first = c;
        else
            ee[u].second = c;
        int v = u;
        while (v)
        {
            seg[v] = max(seg[v * 2] + ee[v].first, seg[v * 2 + 1] + ee[v].second);
            mx[v] = max({mx[v * 2], mx[v * 2 + 1], seg[v * 2] + ee[v].first + seg[v * 2 + 1] + ee[v].second});
            v /= 2;
        }
        cout << mx[1] << '\n';
        lst = mx[1];
        continue;
        st.erase(st.find(c));
        c = e;
        st.insert(c);
        if (n == 2)
        {
            cout << *prev(st.end()) << '\n';
            lst = *prev(st.end());
            continue;
        }
        cout << *prev(st.end()) + *prev(prev(st.end())) << '\n';
        lst = *prev(st.end()) + *prev(prev(st.end()));
        continue;
        long long res = find_diameter();
        cout << res << '\n';
        lst = res;
    }
}

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