제출 #884730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884730		Alish	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	1118 ms	8600 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("connect.in" , "r" , stdin) ; freopen("connect.out" , "w" , stdout);


ll mod = 1e9+7 ;

const int N = 1e5+23;
vector<pll> g[N];
int st[N], ft[N], tim, pos[N];
vector<pair<pll, ll> > E;
ll seg[4*N], lpz[4*N];
int n, q;
ll h[N];
ll ans[N];


pll di;
void dfs(int v, int p=0){
    di=max(di, {h[v], v});
    for (auto pp: g[v]){
        ll u=pp.F, w=ans[pp.S];
        if(u==p) continue;
        h[u]=h[v]+w;
        dfs(u, v);
    }

}




int main()
{
    fast_io
    cin>>n>>q>>mod;
    if(n>5000 || q>5000) return 0;
    for (int i=0; i<n-1; i++){
        ll u, v, w; cin>>v>>u>>w;
        g[v].pb({u, i}); g[u].pb({v, i});
        E.pb({{v, u}, w});
        ans[i]=w;
    }


    ll la=0;
    while(q--){
        ll i, w;
        cin>>i>>w;
        i=(i+la)%(n-1);
        w=(w+la)%mod;
        ans[i]=w;
        di={0, 0};
        dfs(1);
        int r=di.S;
        h[r]=0;

        di={0, 0};
        dfs(r);
        cout<<di.F<<endl;
        la=di.F;

    }

}

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