Submission #716465

#	Time	Username	Problem	Language	Result	Execution time	Memory
716465		parsadox2	Dynamic Diameter (CEOI19_diameter)	C++14	24 / 100	5068 ms	11080 KiB

diameter

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pii  pair<int , int>

const int maxn = 1e5 + 10;
int n , q , dp_down[maxn] , w , mx[2][maxn] , par[maxn] , ch[maxn] , val_par[maxn];
vector <pair<pii , int>> edges;
vector <pii> adj[maxn];
vector <int> all[maxn];

void dfs(int v)
{
	for(auto u : adj[v])  if(u.F != par[v])
	{
		par[u.F] = v;
		val_par[u.F] = u.S;
		dfs(u.F);
		all[v].pb(dp_down[u.F] + u.S);
	}
	sort(all[v].begin() , all[v].end());
	if(!all[v].empty())
		dp_down[v] = all[v].back();
}

void Find_ch(int v , int child)
{
	if(v == 0)  return;
	int tmp = dp_down[child] + val_par[child];
	ch[v] = lower_bound(all[v].begin() , all[v].end() , tmp) - all[v].begin();
	Find_ch(par[v] , v);
}

void Update(int v , int child)
{
	if(v == 0)  return;
	all[v][ch[v]] = dp_down[child] + val_par[child];
	sort(all[v].begin() , all[v].end());
	dp_down[v] = all[v].back();
	Update(par[v] , v);
}

int32_t main()
{
	fast;
	cin >> n >> q >> w;
	for(int i = 0 ; i < n - 1 ; i++)
	{
		int v , u , c;  cin >> v >> u >> c;
		edges.pb({{v , u} , c});
		adj[u].pb({v , c});  adj[v].pb({u , c});
	}
	dfs(1);
	int last = 0;
	while(q--)
	{
		int id , val;  cin >> id >> val;
		id = (id + last) % (n - 1);
		val = (val + last) % w;
		int v = edges[id].F.F , u = edges[id].F.S;
		if(v == par[u])  swap(v , u);
		Find_ch(u , v);
		val_par[v] = val;
		Update(u , v);
		int ans = 0;
		for(int i = 1 ; i <= n ; i++)
		{
			if(SZ(all[i]) == 1)  ans = max(ans , all[i].back());
			if(SZ(all[i]) >= 2)  ans = max(ans , all[i].back() + all[i][SZ(all[i]) - 2]);
		}
		cout << ans << endl;
		last = ans;
	}
	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