Submission #490599

#	Time	Username	Problem	Language	Result	Execution time	Memory
490599		radal	Dynamic Diameter (CEOI19_diameter)	C++14	31 / 100	326 ms	58188 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 = 8e5+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;
}
ll seg[4*N],lz[4*N];
ll h[N];
ll e[N];
pll a[N];
int par[N][20],T,tin[N],tout[N],b[N],l[N];
vector<pair<int,ll>> adj[N];
void dfs(int v,int p){
    par[v][0] = p;
    tin[v] = T;
    b[T] = v;
    T++;
    for (auto u : adj[v]){
        if (u.X == p) continue;
        h[u.X] = u.Y+h[v];
        l[u.X] = l[v]+1;
        dfs(u.X,v);
    }
    tout[v] = T;
    b[T] = v;
    T++;
}
void build(int l,int r,int v){
    if (r-l == 1){
        seg[v] = h[b[l]];
        return;
    }
    int m = (l+r) >> 1,u = (v << 1);
    build(l,m,u);
    build(m,r,u|1);
    seg[v] = max(seg[u],seg[u|1]);
}
void upd(int l,int r,int s,int e,ll x,int v = 1){
    if (l >= s && e >= r){
        seg[v] += x;
        lz[v] += x;
        return;
    }
    if (l >= e || s >= r) return;
    int m = (l+r) >> 1,u = (v << 1);
    if (lz[v]){
        lz[u] += lz[v];
        lz[u|1] += lz[v];
        seg[u] += lz[v];
        seg[u|1] += lz[v];
        lz[v] = 0;
    }
    upd(l,m,s,e,x,u);
    upd(m,r,s,e,x,u|1);
    seg[v] = max(seg[u],seg[u|1]);
}
ll que(int l,int r,int s,int e,int v = 1){
    if (l >= s && e >= r)
        return seg[v];
    if (l >= e || s >= r) return 0;
    int m = (l+r) >> 1,u = (v << 1);
    if (lz[v]){
        lz[u] += lz[v];
        lz[u|1] += lz[v];
        seg[u] += lz[v];
        seg[u|1] += lz[v];
        lz[v] = 0;
    }
    return max(que(l,m,s,e,u),que(m,r,s,e,u|1));
}
inline int getpar(int v,int k){
    repr(i,19,0){
        if (k >= (1 << i)){
            k -= (1 << i);
            v = par[v][i];
        }
    }
    return v;
}
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;
        a[i] = {u,v};
        adj[u].pb({v,d});
        adj[v].pb({u,d});
    }
    dfs(1,0);
    rep(i,0,n-1) if (par[a[i].X][0] == a[i].Y) swap(a[i].X,a[i].Y);
    rep(j,1,20)
        rep(i,2,n+1)
            par[i][j] = par[par[i][j-1]][j-1];
    ll last = 0;
    build(0,T,1);
    multiset<ll> st;
    for (pll u : adj[1])
        st.insert(que(0,T,tin[u.X],tout[u.X]+1));
    while (q--){
        int d;
        ll x;
        cin >> d >> x;
        d = (d+last)%(n-1);
        x = (x+last)%w;
        ll y = a[d].Y;
        int v = getpar(y,l[y]-1);
        st.erase(st.find(que(0,T,tin[v],tout[v]+1)));
        upd(0,T,tin[y],tout[y]+1,x-e[d]);
        st.insert(que(0,T,tin[v],tout[v]+1));
        e[d] = x;
        auto it = st.rbegin();
        last = (*it);
        y = last;
        st.erase(st.find(last));
        if (st.empty()){
            cout << last << endl;
            st.insert(y);
            continue;
        }
        it = st.rbegin();
        last += (*it);
        st.insert(y);
        cout << last << endl;
    }
}

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