Submission #944046

#	Time	Username	Problem	Language	Result	Execution time	Memory
944046		vjudge1	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5031 ms	17356 KiB

diameter

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5;
vector <pair <int,int> > g[N];
int a[N],b[N],c[N],d[N];
void dfs(int v,int p){
    for(auto to : g[v]){
        if(to.ff!=p){
            d[to.ff]=d[v]+c[to.ss];
            dfs(to.ff,v);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n,q,w;
    cin>>n>>q>>w;
    int cnt=0;
    multiset <int> ms;
    for(int i=0;i<n-1;i++){
        cin>>a[i]>>b[i]>>c[i];
        g[a[i]].pb({b[i],i});
        g[b[i]].pb({a[i],i});
        if(1==a[i] or b[i]==1)cnt++;
        ms.insert(c[i]);
    }
    bool sbtsk3=0;
    if(cnt==n-1)sbtsk3=1;
    int last=0;
    for(int i=0;i<q;i++){
        int ind,val;
        cin>>ind>>val;
        ind=(ind+last)%(n-1);
        val=(val+last)%w;
        ms.erase(ms.find(c[ind]));
        ms.insert(val);
        c[ind]=val;
        if(sbtsk3){
            int ans=*ms.rbegin();
            if(ms.size()>=2){
                ms.erase(ms.find(ans));
                int x=*ms.rbegin();
                ms.insert(ans);
                ans+=x;
            }
            cout<<ans<<"\n";
            last=ans;
        }
        else{
            for(int i=1;i<=n;i++)d[i]=0;
            dfs(1,0);
            int root=1,mx=0;
            for(int i=1;i<=n;i++){
                if(mx<d[i]){
                    mx=d[i];root=i;
                }
            }
            for(int i=1;i<=n;i++)d[i]=0;
            dfs(root,0);
            mx=0;
            for(int i=1;i<=n;i++)mx=max(mx,d[i]);
            last=mx;
            cout<<mx<<"\n";
        }
        
    }
}
/*
 
 */

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