Submission #594929

#	Time	Username	Problem	Language	Result	Execution time	Memory
594929		czhang2718	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	614 ms	48328 KiB

diameter

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
const int N=2e5+1;

ll n, q, maxW;
vector<int> adj[N];
int edge[N][2];
ll W[N];
int ti=-1;
int fst[N], lst[N];
vector<int> et;
ll path[N];


ll mx[4*N];
ll mn[4*N];
ll pref[4*N];
ll suf[4*N];
ll seg[4*N];
ll lazy[4*N];

void pull(int x){
    mx[x]=max(mx[2*x+1], mx[2*x+2]);
    mn[x]=min(mn[2*x+1], mn[2*x+2]);
    pref[x]=max({pref[2*x+1], pref[2*x+2], mx[2*x+2]-2*mn[2*x+1]});
    suf[x]=max({suf[2*x+1], suf[2*x+2], mx[2*x+1]-2*mn[2*x+2]});
    // cout << "seg " << x << " = max " << seg[2*x+1] << ", " << seg[2*x+2] << ", " << pref[2*x+2] << "+" << mx[2*x+1] <<", " << mx[2*x+2] << "+" << suf[2*x+1] << "\n"; 
    seg[x]=max({seg[2*x+1], seg[2*x+2], pref[2*x+2]+mx[2*x+1], mx[2*x+2]+suf[2*x+1]});
}

void push(int x, int lx, int rx){
    if(rx-lx==1) return;
    ll v=lazy[x];
    for(int y:{2*x+1, 2*x+2}){
        mx[y]+=v;
        mn[y]+=v;
        pref[y]-=v;
        suf[y]-=v;
        lazy[y]+=v;
    }
    lazy[x]=0;
}

void add(int l, int r, ll v, int x, int lx, int rx){
    if(lx>=r || rx<=l) return;
    push(x, lx, rx);
    if(lx>=l && rx<=r){
        lazy[x]=v;
        mx[x]+=v;
        mn[x]+=v;
        pref[x]-=v;
        suf[x]-=v;
        // cout << x << " " << lx << " " << rx << " " << pref[x] << " " << suf[x] << "\n";
        return;
    }
    int m=(lx+rx)/2;
    add(l,r,v,2*x+1,lx,m);
    add(l,r,v,2*x+2,m,rx);
    
    pull(x);
    // cout << x << " seg " << lx << " " << rx << " = " << seg[x] << "\n";
}

void add(int l, int r, ll v){ add(l,r,v,0,0,2*n-1); }




void dfs(int x, int par){
    et.push_back(x);
    for(int e:adj[x]){
        int u=(edge[e][0]==x?edge[e][1]:edge[e][0]);
        if(u==par) continue;
        path[u]=path[x]+W[e];
        dfs(u, x);
        et.push_back(x);
    }
}


int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> q >> maxW;
    for(int i=0; i<n-1; i++){
        int u,v; ll w; cin >> u >> v >> w;
        edge[i][0]=u; edge[i][1]=v; 
        W[i]=w;
        adj[u].push_back(i);
        adj[v].push_back(i);
    }

    dfs(1, 0);

    for(int i=1; i<=n; i++) fst[i]=1e9, lst[i]=-1;

    for(int t=0; t<2*n-1; t++){
        fst[et[t]]=min(fst[et[t]], t);
        lst[et[t]]=max(lst[et[t]], t);
    }

    for(int i=0; i<n-1; i++){
        if(path[edge[i][0]]<path[edge[i][1]]) swap(edge[i][0], edge[i][1]);
        int v=edge[i][0];
        // cout << "add " << fst[v] << " " << lst[v] << " " << path[v] << "\n"; 
        add(fst[v], lst[v]+1, W[i]);
    }
   // for(int i=0; i<2*n-1; i++){
   //  add(i,i+1,i+1);
   // }
    // for(int i=0; i<2*n-1; i++){
    //     cout << 
    // }
    // cout << seg[0] << "\n";

    ll ans=0;
    while(q--){
        ll i, w; cin >> i >> w;
        i=(i+ans)%(n-1);
        w=(w+ans)%maxW;
        int u=edge[i][0];
        add(fst[u], lst[u]+1, w-W[i]);
        W[i]=w;
        cout << (ans=seg[0]) << "\n";
    }   
}

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