Submission #718520

#	Time	Username	Problem	Language	Result	Execution time	Memory
718520		amirhoseinfar1385	Dynamic Diameter (CEOI19_diameter)	C++17	11 / 100	5071 ms	13516 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
long long n,q,w;
struct yal{
	long long u,v,w,par;
	yal(){
		u=v=w=par=0;
	}
	int getad(int fu){
		int ret=(fu^u^v);
		return ret;
	}
};
vector<vector<int>>adj;
vector<yal>alled;
vector<long long>allv;

void solve(int u,int par=0,long long len=0){
	allv.push_back(len);
	for(auto x:adj[u]){
		int v=alled[x].getad(u);
		if(v!=par){
			solve(v,u,len+alled[x].w);
			allv.push_back(len);
		}
	}
}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>w;
	alled.resize(n+1);
	adj.resize(n+1);
	for(int i=0;i<n-1;i++)
	{
		cin>>alled[i].u>>alled[i].v>>alled[i].w;
		adj[alled[i].u].push_back(i);
		adj[alled[i].v].push_back(i);
	}
	long long lasta=0;
	for(int i=0;i<q;i++){
		long long we,e;
		cin>>e>>we;
		e=(e+lasta)%(n-1);
		we=(we+lasta)%(w);
		alled[e].w=we;
		allv.clear();
		solve(1);
		//cout<<e<<" "<<we<<" "<<alled[e].u<<" "<<alled[e].v<<"\n";
		//for(int j=0;j<(int)allv.size();j++){
		//	cout<<allv[j]<<" ";
		//}
		//cout<<'\n';
		long long res=0;
		for(int i1=0;i1<(int)allv.size();i1++){
			for(int i2=i1;i2<(int)allv.size();i2++){
				for(int i3=i2;i3<(int)allv.size();i3++){
					res=max(res,allv[i1]+allv[i3]-allv[i2]*2);
				}
			}	
		}
		cout<<res<<"\n";
		lasta=res;
	}
}

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