Submission #490601

#	Time	Username	Problem	Language	Result	Execution time	Memory
490601		radal	Dynamic Diameter (CEOI19_diameter)	C++14	24 / 100	5073 ms	8036 KiB

diameter

#include <bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
typedef pair<long double,long double> pld;
const long long int N = 1e5+10,mod = 1e9+7,inf = 1e9,sq = 700,sig = 26;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,int k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
vector<pll> adj[N];
ll e[N];
ll h[N];
int dfs(int v,int p){
    ll mx = h[v];
    int w = v;
    for (pll u : adj[v]){
        if(u.X == p) continue;
        h[u.X] = h[v]+e[u.Y];
        int x = dfs(u.X,v);
        if (h[x] > mx){
            mx = h[x];
            w = x;
        }
    }
    return w;
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);cout.tie(0);
    int n,q;
    ll w;
    cin >> n >> q >> w;
    rep(i,0,n-1){
        int u,v;
        ll d;
        cin >> u >> v >> d;
        e[i] = d;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
    }
    ll last = 0;
    while (q--){
        int d;
        ll x;
        cin >> d >> x;
        d = (d+last)%(n-1);
        x = (x+last)%w;
        e[d] = x;
        h[1] = 0;
        int u = dfs(1,-1);
        h[u] = 0;
        int v = dfs(u,-1);
        cout << h[v] << endl;
        last = h[v];
    }
    return 0;
}

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