Submission #716529

#	Time	Username	Problem	Language	Result	Execution time	Memory
716529		KING	Dynamic Diameter (CEOI19_diameter)	C++14	24 / 100	5058 ms	11496 KiB

diameter

#include<bits/stdc++.h>
#define NOT_STONKS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using namespace std;
const int maxn = 2e5 + 10; //4e6 + 10; //3e5 + 10;
const int mod = 1e9 + 7; //998244353;
typedef long long ll;

ll n, q, w, f[maxn], s[maxn], dis[maxn];
vector< pair<ll, ll> > adj[maxn];
pair<ll, ll> temp;
pair< pair<ll, ll>, ll > edge[maxn];

void dfs(int v, int par = -1) {
    for (auto [ u, x ] : adj[v]) if (u != par) {
        dfs(u, v);
        if (par != -1) {
            f[v] = f[u];
            s[v] = s[u] + x;
        }
    }
    if (adj[v].size() == 1 && par != -1)
        f[v] = v;
}

void trav(int v, int par = -1) {
    for (auto [ u, x ] : adj[v]) if (u != par) {
        dis[u] = dis[v] + x;
        temp = max(temp, { dis[u], u });
        trav(u, v);
    }
}

int main() {
    NOT_STONKS;

    cin >> n >> q >> w;
    for (int i = 0; i < n - 1; i++) {
        int u, v, x;
        cin >> u >> v >> x;
        edge[i] = { { u, v }, x };
        adj[u].push_back({ v, x });
        adj[v].push_back({ u, x });
    }
    
    ll last = 0;
    if (adj[1].size() == n - 1) {
        dfs(1);
        multiset<ll> m;
        for (auto [ u, _ ] : adj[1]) 
            m.insert(s[u]);

        while (q--) {
            int d, e;
            cin >> d >> e;
            d = (d + last) % (n - 1);
            e = (e + last) % w;

            int E = max(edge[d].first.first, edge[d].first.second);
            m.erase(m.find(s[E])); 
            s[E] = e;
            m.insert(s[E]);

            multiset<ll>::iterator it = m.begin();
            last = *it;
            it++;
            last += *it;
            cout << last << '\n';
        }
    } else {
        while (q--) {
            int d, e;
            cin >> d >> e;
            d = (d + last) % (n - 1);
            e = (e + last) % w;
            
            auto E = edge[d];
            int id1 = find(adj[E.first.first].begin(), adj[E.first.first].end(), make_pair(E.first.second, E.second)) - adj[E.first.first].begin();
            int id2 = find(adj[E.first.second].begin(), adj[E.first.second].end(), make_pair(E.first.first, E.second)) - adj[E.first.second].begin();
            adj[E.first.first].erase(adj[E.first.first].begin() + id1);
            adj[E.first.second].erase(adj[E.first.second].begin() + id2);
            
            edge[d] = { E.first, e };
            adj[E.first.first].push_back({ E.first.second, e });
            adj[E.first.second].push_back({ E.first.first, e });
            
            temp = { 0, 0 };
            dis[1] = 0;
            trav(1);
            dis[temp.second] = 0;
            trav(temp.second);
            last = temp.first;
            cout << last << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void dfs(int, int)':
diameter.cpp:15:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |     for (auto [ u, x ] : adj[v]) if (u != par) {
      |               ^
diameter.cpp: In function 'void trav(int, int)':
diameter.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for (auto [ u, x ] : adj[v]) if (u != par) {
      |               ^
diameter.cpp: In function 'int main()':
diameter.cpp:47:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   47 |     if (adj[1].size() == n - 1) {
      |         ~~~~~~~~~~~~~~^~~~~~~~
diameter.cpp:50:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |         for (auto [ u, _ ] : adj[1])
      |                   ^

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