Submission #1104742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104742		theSkeleton	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	106 ms	24332 KiB

diameter

#include<bits/stdc++.h>
#define space <<' '<<
#define endl '\n'
#define inf 1e14
#define F first
#define S second
#define PB push_back
#define PF push_front
#define md(a) ((a+mod)%mod)
#define MP(a,b) make_pair(a,b)
#define MT(a,b,c) make_tuple(a,b,c)
typedef long long ll;
using namespace std;
template<typename t> using heap=
priority_queue<t,vector<t>,greater<t>>;
const int mx = 1e5+5;
ll edgw[mx],lvl[mx];
pair<int,int> edg[mx];
int st[mx],ed[mx],g[mx],c;
vector<pair<int,ll>>adj[mx];
ll seg[mx*4],lazy[mx*4],dis[mx];
void push(int u,int l,int r){
    if(l==r) seg[u]+=lazy[u];
    else{
        seg[u]+=lazy[u];
        lazy[u*2]+=lazy[u];
        lazy[u*2+1]+=lazy[u];
    }
    lazy[u]=0;
}
void build(int u=1,int l=1,int r=c){
    if(l==r) seg[u]=dis[g[l]];
    else{
        int m=(l+r)/2;
        build(u*2,l,m);
        build(u*2+1,m+1,r);
        seg[u]=max(seg[u*2],seg[u*2+1]);
    }
}
void upd(int L,int R,ll v,int u=1,int l=1,int r=c){
    push(u,l,r);
    if(L<=l&&r<=R){
        lazy[u]+=v;
        push(u,l,r);
    }
    else if(!(R<l||r<L)){
        int m=(l+r)/2;
        upd(L,R,v,u*2,l,m);
        upd(L,R,v,u*2+1,m+1,r);
        seg[u]=max(seg[u*2],seg[u*2+1]);
    }
}
void dfs(int v){
    st[v]=++c;
    g[c]=v;
    for(auto e:adj[v])
        if(st[e.F]==0)
            lvl[e.F]=lvl[v]+1
            ,dis[e.F]=dis[v]+e.S
            ,dfs(e.F);
    ed[v]=c;
}
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll n,q,w;cin>>n>>q>>w;
    for(ll u,v,w,t=0;t<n-1;t++){
        cin>>u>>v>>w;
        edgw[t]=w;
        edg[t]=MP(u,v);
        adj[u].PB(MP(v,w));
        adj[v].PB(MP(u,w));
    }
    dfs(1);
    build();
    for(ll l=0,d,e;q--;){
        cin>>d>>e;
        e=(l+e)%w;
        d=(l+d)%(n-1);
        int u=edg[d].F,v=edg[d].S;
        if(lvl[v]<lvl[u])swap(u,v);
        ll dif=e-edgw[d];edgw[d]=e;
        upd(st[v],ed[v],dif);
        l=seg[1];
        cout<<l<<endl;
    }
    return 0;
}

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