Submission #884794

#	Time	Username	Problem	Language	Result	Execution time	Memory
884794		Alish	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	200 ms	72616 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 = 2e5+23;
vector<pll> g[N];
int st[N], ft[N], tim;
vector<pair<pll, ll> > E;


struct Node{
    ll  pref, suff, sum, allans;
    ll ans, prefans, suffans;

}seg[4*N];

int n, q;
ll h[N];
ll ans[N];

vector<ll> vec;
pii pos[N];


void dfs(int v, int p=0){

    for (auto pp: g[v]){
        ll u=pp.F, w=ans[pp.S];
        if(u==p) continue;
        vec.pb(w);
        pos[pp.S].F=(vec.size()-1);
        h[u]=h[v]+w;
        dfs(u, v);
        vec.pb(-w);
        pos[pp.S].S=(vec.size()-1);
    }

}

void Merge(int ind){

    seg[ind].pref=max(seg[2*ind+1].pref, seg[2*ind+1].sum+seg[2*ind+2].pref);
	seg[ind].suff=max(seg[2*ind+2].suff, -seg[2*ind+2].sum+seg[2*ind+1].suff);

	seg[ind].sum=seg[2*ind+1].sum+seg[2*ind+2].sum;

	seg[ind].allans=max(seg[2*ind+1].allans+seg[2*ind+2].sum, -seg[2*ind+1].sum+seg[2*ind+2].allans);

	seg[ind].prefans=max({seg[2*ind+1].prefans, seg[2*ind+1].allans+seg[2*ind+2].pref, -seg[2*ind+1].sum+seg[2*ind+2].prefans});
	seg[ind].suffans=max({seg[2*ind+2].suffans, seg[2*ind+2].allans+seg[2*ind+1].suff, seg[2*ind+2].sum+seg[2*ind+1].suffans});

	seg[ind].ans=max({seg[2*ind+1].ans, seg[2*ind+2].ans, seg[2*ind+1].suffans+seg[2*ind+2].pref, seg[2*ind+1].suff+seg[2*ind+2].prefans});

}

void build(int l=0, int r=vec.size(), int ind=0){

    if(r-l==1){
        seg[ind].pref=max(0LL, vec[l]);
        seg[ind].suff=max(0LL, -vec[l]);
		seg[ind].ans=seg[ind].prefans=seg[ind].suffans=seg[ind].allans=abs(vec[l]);
		seg[ind].sum=vec[l];
        return;
    }
    int mid=(r+l)>>1;
    build(l, mid, 2*ind+1); build(mid, r, 2*ind+2);

    Merge(ind);
}

void upd(int i, ll v, int l=0, int r=vec.size(), int ind=0){
    if(r-l==1){
        vec[l]=v;
         seg[ind].pref=max(0LL, vec[l]);
        seg[ind].suff=max(0LL, -vec[l]);
		seg[ind].ans=seg[ind].prefans=seg[ind].suffans=seg[ind].allans=abs(vec[l]);
		seg[ind].sum=vec[l];
        return;
    }
    int mid=(r+l)>>1;
    if(i<mid) upd(i, v, l, mid, 2*ind+1);
    else upd(i, v, mid, r, 2*ind+2);

    Merge(ind);
}




int main()
{
    fast_io
    cin>>n>>q>>mod;

    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;
    }

    dfs(1);
    build();
    ll la=0;
    while(q--){
        ll i, w;
        cin>>i>>w;
        i=(i+la)%(n-1);
        w=(w+la)%mod;
        upd(pos[i].F, w);
        upd(pos[i].S, -w);
        la=seg[0].ans;
        cout<<la<<endl;
    }

}

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