Submission #884805

#	Time	Username	Problem	Language	Result	Execution time	Memory
884805		1L1YA	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	150 ms	27804 KiB

diameter

//1L1YA
#include<bits/stdc++.h>
using namespace std;
#define ll           long long
#define Pb           push_back
#define dokme(x)     cout << x << endl, exit(0)
#define pll          pair<ll,ll>
#define F            first
#define S            second
#define endl         '\n'
#define sep          ' '
#define all(x)       x.begin(),x.end()
#define FastIO       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lc           id<<1
#define rc           lc|1

const ll mod=1e9+7;
const ll oo=4e18;
const int N=1e5+5;
const int lg=23;

ll n,q,W,T,lst,a[N],h[N],st[N],et[N],wp[N],par[N],lz[N<<2];
pll seg[N<<2];
vector<pll> E,adj[N];

void shift(int id){
    seg[lc].F+=lz[id];lz[lc]+=lz[id];
    seg[rc].F+=lz[id];lz[rc]+=lz[id];
    lz[id]=0;
}

void modify(int pos,ll val,int id=1,int l=1,int r=n+1){
    if(r-l==1){
        seg[id].F=val;
        seg[id].S=l;
        return;
    }
    int mid=l+r>>1;
    if(pos<mid)    modify(pos,val,lc,l,mid);
    else    modify(pos,val,rc,mid,r);
    if(seg[lc].F>seg[rc].F)    seg[id]=seg[lc];
    else    seg[id]=seg[rc];
}

void update(int ql,int qr,ll val,int id=1,int l=1,int r=n+1){
    if(qr<=l || ql>=r)    return;
    if(ql<=l && r<=qr){
        seg[id].F+=val;
        lz[id]+=val;
        return;
    }
    int mid=l+r>>1;
    shift(id);
    update(ql,qr,val,lc,l,mid);
    update(ql,qr,val,rc,mid,r);
    if(seg[lc].F>seg[rc].F)    seg[id]=seg[lc];
    else    seg[id]=seg[rc];
}

pll get(int ql,int qr,int id=1,int l=1,int r=n+1){
    if(qr<=l || ql>=r)    return {-1,0};
    if(ql<=l && r<=qr)    return seg[id];
    int mid=l+r>>1;
    shift(id);
    pll p1=get(ql,qr,lc,l,mid),p2=get(ql,qr,rc,mid,r);
    if(p1.F>p2.F)    return p1;
    else    return p2;
}

void dfs(int v,int p=-1){
    st[v]=T++;
    a[st[v]]=v;
    for(auto [u,w]: adj[v])
        if(u!=p){
            h[u]=h[v]+w;
            par[u]=v;
            wp[u]=w;
            dfs(u,v);
        }
    et[v]=T;
}

void calc(){
    pll p=get(1,n+1);
    int v=a[p.S];
    int l=0,r=adj[1].size();
    while(r-l>1){
        int mid=l+r>>1;
        if(st[adj[1][l].F]<=st[v])    l=mid;
        else    r=mid;
    }
    int u=adj[1][l].F;
    ll ans=0;
    ans=max(ans,get(1,st[u]).F);
    if(et[u]!=n+1)
        ans=max(ans,get(et[u],n+1).F);
    ans=ans+p.F;
    cout << ans << endl;
    lst=ans;
}

int main(){
    FastIO

    cin >> n >> q >> W;
    for(int i=1;i<n;i++){
        ll u,v,w;
        cin >> u >> v >> w;
        adj[u].Pb({v,w});
        adj[v].Pb({u,w});
        E.Pb({u,v});
    }
    T=1;
    dfs(1);
    for(int i=1;i<=n;i++)
        modify(st[i],h[i]);
    for(int i=1;i<n;i++)
        if(E[i].F!=par[E[i].S])
            swap(E[i].F,E[i].S);
    while(q--){
        ll i,x;
        cin >> i >> x;
        i=(i+lst)%(n-1);
        x=(x+lst)%W;
        int u=E[i].F,v=E[i].S;
        update(st[v],et[v],x-wp[v]);
        wp[v]=x;
        calc();
    }

    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void modify(int, long long int, int, int, int)':
diameter.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid=l+r>>1;
      |             ~^~
diameter.cpp: In function 'void update(int, int, long long int, int, int, int)':
diameter.cpp:52:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid=l+r>>1;
      |             ~^~
diameter.cpp: In function 'std::pair<long long int, long long int> get(int, int, int, int, int)':
diameter.cpp:63:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int mid=l+r>>1;
      |             ~^~
diameter.cpp: In function 'void calc()':
diameter.cpp:88:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |         int mid=l+r>>1;
      |                 ~^~
diameter.cpp: In function 'int main()':
diameter.cpp:125:13: warning: unused variable 'u' [-Wunused-variable]
  125 |         int u=E[i].F,v=E[i].S;
      |             ^

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