Submission #1220195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220195		Trumling	Dynamic Diameter (CEOI19_diameter)	C++20	0 / 100	578 ms	1114112 KiB

diameter

//Trumling ©
//Αφόδευε υψηλά και ηγνάντει 
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 998244353
#define all(x) x.begin(),x.end()
vector<vector<pair<ll,ll>>>g;
vector<ll>d;
vector<pair<ll,ll>>depth;
ll ans=0;
void dia(int start)
{
    if(g[start].size()==1)
        return ;

    pair<ll,ll> l=g[start][0];
    pair<ll,ll> r=g[start][1];

    dia(l.F);
    dia(r.F);

    depth[start].F=depth[l.F].S + d[l.S] + depth[r.F].S + d[r.S];
    depth[start].F=max(depth[l.F].F,depth[r.F].F);
    depth[start].S=max(depth[l.F].S + d[l.S] , depth[r.F].S + d[r.S]);
}

void update(int start)
{
    while(start!=1)
    {
        pair<ll,ll> l=g[start][0];
        pair<ll,ll> r=g[start][1];
        
        depth[start].F=depth[l.F].S + d[l.S] + depth[r.F].S + d[r.S];
        depth[start].F=max(depth[l.F].F,depth[r.F].F);
        depth[start].S=max(depth[l.F].S + d[l.S] , depth[r.F].S + d[r.S]);

        start/=2;
    }
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n,q,w;
cin>>n>>q>>w;
g.assign(n+1,vector<pair<ll,ll>>());
d.assign(n,0);
depth.assign(n,{0,0});
ll par[n-1];
for(int i=0;i<n-1;i++)
{
ll x,y,z;
cin>>x>>y>>z;

g[x].pb({y,i});
g[y].pb({x,i});
d[i]=z;
par[i]=min(x,y);
}

ll last=0;
dia(1);
while(q--)
{
    ll x,y;
    cin>>x>>y;
    x=(x+last)%(n-1);
    y=(y+last)%w;

    //cout<<x<<' '<<y<<'\n';
    d[x]=y;
    update(par[x]);
    ans=depth[1].F;
    cout<<ans<<'\n';
    last=ans;
}

}

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