제출 #762834

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

diameter

#include<bits/stdc++.h>

using namespace std;

#define f(i,a,b) for(ll i=a;i<b;i++)
#define af(i,a,b) for(int i=a;i>=b;i--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define PB push_back
#define MP make_pair
#define F first
#define S second

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

const ll mod=998244353;
const int maxN=1e5+5;
const ll inf=1e12;

vector<pll> adj[maxN];
ll dist[maxN];
//ll vis[maxN];
ll n,q,w;
vector<vector<ll>> ed;

/*pll dij(ll a){
	priority_queue<pll> q;
	q.push(MP(0,a));
	f(i,1,n+1) dist[i]=0;
	f(i,1,n+1) vis[i]=0;
	dist[a]=0;
	while(!q.empty()){
		a=q.top().S;
		q.pop();
		if(vis[a]==1) continue;
		vis[a]=1;
		for(auto x:adj[a]){
			if(dist[x.F]<dist[a]+x.S){
				dist[x.F]=dist[a]+x.S;
				q.push(MP(dist[x.F],x.F));
			}
		}
	}
	ll res=0,d=-1;
	f(i,1,n+1){
		if(d<dist[i]){
			d=dist[i];
			res=i;
		}
	}
	return MP(res,d);
}*/

void dfs(ll a, ll p){
	for(auto x:adj[a]){
		if(x.F==p) continue;
		dist[x.F]=dist[a]+x.S;
		dfs(x.F,a);
	}
}

ll root(ll a){
	f(i,1,n+1) dist[i]=-1;
	dist[a]=0;
	ll res=0,d=-1;
	dfs(a,-1);
	f(i,1,n+1){
		//cout<<dist[i]<<" ";
		if(d<dist[i]){
			d=dist[i];
			res=i;
		}
	}
	return res;
}

void bin(ll a, ll b){
	int x1=ed[a][0];
	int x2=ed[a][1];
	int beg=0;
	int end=adj[x1].size()-1;
	int res=-1;
	while(beg<=end){
		int mid=(beg+end)/2;
		if(adj[x1][mid].F<=x2){
			res=mid;
			beg=mid+1;
		}
		else end=mid-1;
	}
	adj[x1][res].S=b;

	beg=0;
	end=adj[x2].size()-1;
	res=-1;
	while(beg<=end){
		int mid=(beg+end)/2;
		if(adj[x2][mid].F<=x1){
			res=mid;
			beg=mid+1;
		}
		else end=mid-1;
	}
	adj[x2][res].S=b;
}

void go(){
	ll a,b,c;
	cin>>n>>q>>w;
	ed.PB({0,0,0});
	f(i,0,n-1){
		cin>>a>>b>>c;
		ed.PB({a,b,c});
		adj[a].PB(MP(b,c));
		adj[b].PB(MP(a,c));
	}
	f(i,1,n+1){
		sort(adj[i].begin(),adj[i].end());
	}
	ll last=0;
	f(i,0,q){
		cin>>a>>b;
		a=(a+last)%(n-1)+1;
		b=(b+last)%w;
		bin(a,b);
		ed[a][2]=b;
		last=dist[root(root(a))];
		cout<<last<<"\n";
	}
}

int main(){
	fastio;
	int test=1;
	//cin>>test;
	f(i,1,test+1){
		//cout<<"Case "<<i<<":\n";
		go();
	}

	return 0;
}

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