Submission #1104671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104671		sinataghizadeh	Dynamic Diameter (CEOI19_diameter)	C++14	0 / 100	48 ms	844 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

//typedef int       ll;
typedef pair<int, int>  pii;
//typedef pair<ll, ll>  pll;
#define all(x)			(x).begin(),(x).end()
#define pb    			push_back
#define fi              first
#define se              second
#define beg             begin
#define siz              size()
#define fastio          cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define endl       		'\n'
#define ins             insert
#define log             LOG
//const ll inf = 1e9;
//const ll mod = 10289;
const int maxn=5002;
const int log=24;
int n,q,dis[maxn],w,mx;
vector<int>adj[maxn];
map<pii,int>x;
vector<pii>ed;
void dfs(int v,int p){
	for(auto u:adj[v]){
		if(p==u)continue;
		dis[u]=dis[v]+x[{u,v}];
		dfs(u,v);
	}
	if(dis[v]>dis[mx])mx=v;
}
int main(){
	fastio
	cin>>n>>q>>w;
	for(int i=1;i<n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		x[{a,b}]=c;
		x[{b,a}]=c;
		ed.pb({a,b});
		adj[a].pb(b);adj[b].pb(a);
	}
	int ld=0;
	while(q--){
		int d,e;
		cin>>d>>e;d+=ld;e+=ld;d%=(n-1);e%=w;
		int u=ed[d].fi,v=ed[d].se;
		x[{u,v}]=e;x[{v,u}]=e;
		dis[1]=0;
		dfs(1,-1);
		dis[mx]=0;
		dfs(mx,-1);
		cout<<dis[mx]<<endl;
		ld=dis[mx];
	}
	
}

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