Submission #716478

#	Time	Username	Problem	Language	Result	Execution time	Memory
716478		parsadox2	Dynamic Diameter (CEOI19_diameter)	C++14	49 / 100	2184 ms	20804 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];
multiset <int> fbi;

int Find_ans(int v)
{
	int res = 0;
	if(SZ(all[v]) >= 1)  res += all[v].back();
	if(SZ(all[v]) >= 2)  res += all[v][SZ(all[v]) - 2];
	return res;
}

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();
	fbi.insert(Find_ans(v));
}

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();
	tmp = Find_ans(v);
	auto it = fbi.find(tmp);
	fbi.erase(it);
	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();
	fbi.insert(Find_ans(v));
	Update(par[v] , v);
}

int32_t main()
{
	fast;
	cin >> n >> q >> w;
	bool ok = true;
	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});
		if(v != 1 && u != 1)  ok = false;
	}
	if(ok)
	{
		multiset <int> st;
		for(auto u : edges)  st.insert(u.S);
		int last = 0;
		while(q--)
		{
			int id , val;  cin >> id >> val;
			id = (id + last) % (n - 1);
			val = (val + last) % w;
			auto it = st.find(edges[id].S);
			st.erase(it);
			st.insert(val);
			edges[id].S = val;
			it = st.end();
			it--;
			if(SZ(st) == 1)  last = *it;
			if(SZ(st) >= 2)
			{
				last = *it;
				it--;
				last += *it;
			}
			cout << last << endl;
		}
		return 0;
	}
	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);
		auto it = fbi.end();
		it--;
		int ans = *it;
		cout << ans << endl;
		last = ans;
	}
	return 0;
}

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