Submission #557293

#	Time	Username	Problem	Language	Result	Execution time	Memory
557293		fatemetmhr	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	5062 ms	21972 KiB

diameter

//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

ll h[maxn5], c[maxn5];
vector <pair<int, ll>> adj[maxn5];
int a[maxn5], b[maxn5];

inline void dfs(int v, int par){
    for(auto [u, id] : adj[v]) if(u != par){
        h[u] = h[v] + c[id];
        dfs(u, v);
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

 
    ll w;
    int n, q; cin >> n >> q >> w;
 
    for(int i = 0; i < n - 1; i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        adj[a[i]].pb({b[i], i});
        adj[b[i]].pb({a[i], i});
    }

    ll last = 0;

    for(int i = 0; i < q; i++){
        ll d, e; cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;

        c[d] = e;
        h[0] = 0;
        dfs(0, -1);
        int di = 0;
        for(int i = 0; i < n; i++) if(h[i] >= h[di])
            di = i;
        h[di] = 0;
        dfs(di, -1);
        last = 0;
        for(int i = 0; i < n; i++)
            last = max(last, h[i]);
        cout << last << '\n';

    }
}

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