Submission #490600

#	Time	Username	Problem	Language	Result	Execution time	Memory
490600		radal	Dynamic Diameter (CEOI19_diameter)	C++14	18 / 100	261 ms	9536 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];
int e[N],seg[N*4];
pll E[N];
int dp[N],n;
void dfs(int v){
    for (pll u : adj[v]){
        dfs(u.X);
        dp[v] = max(dp[v],dp[u.X]+e[u.Y]);
    }
}
void build(int l,int r,int v){
    if (r-l == 1){
        for (pll u : adj[l]) seg[v] += dp[u.X]+e[u.Y];
        return;
    }
    int m = (l+r) >> 1;
    build(l,m,2*v);
    build(m,r,2*v+1);
    seg[v] = max(seg[2*v],seg[2*v+1]);
}
void upd(int l,int r,int v,int p){
    if (r-l == 1){
        seg[v] = 0;
        for (pll u : adj[l])
            seg[v] += dp[u.X]+e[u.Y];
        
        return;
    }
    int m = (l+r) >> 1, u = (v << 1);
    if (p < m) upd(l,m,u,p);
    else upd(m,r,u+1,p);
    seg[v] = max(seg[u|1],seg[u]);
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);cout.tie(0);
    int q;
    ll w;
    cin >> n >> q >> w;
    rep(i,0,n-1){
        int u,v;
        ll d;
        cin >> u >> v >> d;
        e[i] = d;
        if (u > v) swap(u,v);
        E[i] = {u,v};
        adj[u].pb({v,i});
    }
    ll last = 0;
    dfs(1);
    build(1,n+1,1);
    while (q--){
        int d;
        ll x;
        cin >> d >> x;
        d = (d+last)%(n-1);
        x = (x+last)%w;
        e[d] = x;
        int v = E[d].X;
        while (v){
            dp[v] = 0;
            for (pll u : adj[v])
                dp[v] = max(dp[v],dp[u.X]+e[u.Y]);
            upd(1,n+1,1,v);
            v >>= 1;
        }
        last = seg[1];
        cout << last << endl;
    }
    return 0;
}

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