Submission #718521

#	Time	Username	Problem	Language	Result	Execution time	Memory
718521		parsadox2	Dynamic Diameter (CEOI19_diameter)	C++14	11 / 100	1216 ms	3444 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());

const int maxn = 1e2 + 10;
int n , w , q , st[maxn] , fn[maxn] , dis[maxn] , par[maxn];
vector <pair<int , int>> adj[maxn];
vector <int> trav;

void dfs(int v , int p = -1)
{
	st[v] = SZ(trav);
	trav.pb(dis[v]);
	for(auto u : adj[v])  if(u.F != p)
	{
		par[u.F] = v;
		dis[u.F] = dis[v] + u.S;
		dfs(u.F , v);
		trav.pb(dis[v]);
	}
	fn[v] = SZ(trav);
}

void Add(int v , int val)
{
	for(int i = st[v] ; i < fn[v] ; i++)  trav[i] += val;
}

int solve()
{
	int res = 0;
	for(int i = 0 ; i < SZ(trav) ; i++)
		for(int j = i ; j < SZ(trav) ; j++)
			for(int k = j ; k < SZ(trav) ; k++)
				res = max(res , trav[i] + trav[k] - 2 * trav[j]);
	return res;
}

int32_t main()
{
	fast;
	cin >> n >> q >> w;
	vector <pair<pair<int , int> , int>> edges;
	for(int i = 0 ; i < n -1 ; i++)
	{
		int v , u , c;  cin >> v >> u >> c;
		adj[v].pb({u , c});  adj[u].pb({v , c});
		edges.pb({{u , v} , c});
	}
	dfs(1);
	int last = 0;
	while(q--)
	{
		int id , val;  cin >> id >> val;
		id = (id + last) % (n - 1);
		val = (val + last) % w;
		auto u = edges[id];
		int v = u.F.F;
		if(par[v] != u.F.S)  v = u.F.S;
		int tmp = (val - u.S);
		Add(v , tmp);
		last = solve();
		edges[id].S = val;
		cout << last << '\n';
	}
	return 0;
}

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