Submission #1104589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104589		sinataghizadeh	Dynamic Diameter (CEOI19_diameter)	C++14	11 / 100	5055 ms	2896 KiB

diameter

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


typedef long long       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=5004+6;
const int log=24;
ll n,q,vis[maxn],dis[maxn],w;
vector<ll>adj[maxn];
map<pll,ll>x;
vector<pll>ed;
void dfs(ll v,ll p){
	for(auto u:adj[v]){
		if(p==u)continue;
		dis[u]=dis[v]+x[{u,v}];
		dfs(u,v);
	}
}
int main(){
	fastio
	cin>>n>>q>>w;
	for(int i=1;i<n;i++){
		ll 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);
	}
	ll ld=0;
	while(q--){
		ll d,e;
		cin>>d>>e;d+=ld;e+=ld;d%=(n-1);e%=w;
		ll u=ed[d].fi,v=ed[d].se;
		x[{u,v}]=e;x[{v,u}]=e;
		ll mx=0;dis[1]=0;
		//fill(dis,dis+n+2,0);
		dfs(1,-1);
		for(int i=0;i<=n;i++){
			if(dis[i]>dis[mx])mx=i;
		}dis[mx]=0;
	//	fill(dis,dis+n+2,0);
		dfs(mx,-1);
		for(int i=0;i<=n;i++){
			if(dis[i]>dis[mx])mx=i;
		}
		cout<<dis[mx]<<endl;
		ld=dis[mx];
	}
	
}

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