Submission #718632

#	Time	Username	Problem	Language	Result	Execution time	Memory
718632		parsadox2	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	462 ms	91508 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 int long long
const int maxn = 3e5 + 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);
}

struct nod{
	int mx , mxmn , mnmx , ans , mn , lzy;
	nod()
	{
		lzy = 0;
	}
} tree[(maxn << 2)];

nod Merge(nod a , nod b)
{
	nod res;
	res.mx = max(a.mx , b.mx);
	res.mn = min(a.mn , b.mn);
	res.mxmn = max({a.mxmn , b.mxmn , a.mx - (b.mn << 1)});
	res.mnmx = max({a.mnmx , b.mnmx , b.mx - (a.mn << 1)});
	res.ans = max({a.ans , b.ans , a.mxmn + b.mx , a.mx + b.mnmx});
	return res;
}

void Build(int node = 1 , int nl = 0 , int nr = SZ(trav))
{
	if(nr - nl == 1)
	{
		tree[node].mx = tree[node].mn = trav[nl];
		tree[node].mxmn = tree[node].mnmx = -trav[nl];
		tree[node].ans = 0;
		return;
	}
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	Build(lc , nl , mid);  Build(rc , mid , nr);
	tree[node] = Merge(tree[lc] , tree[rc]);
}

void add(int node , int val)
{
	tree[node].lzy += val;
	tree[node].mx += val;
	tree[node].mn += val;
	tree[node].mxmn -= val;
	tree[node].mnmx -= val;
}

void Shift(int node)
{
	int lc = node << 1 , rc = lc | 1;
	add(lc , tree[node].lzy);  add(rc , tree[node].lzy);
	tree[node].lzy = 0;
}

void Add(int l , int r , int val , int node = 1 , int nl = 0 , int nr = SZ(trav))
{
	if(r <= nl || nr <= l)  return;
	if(l <= nl && nr <= r)
	{
		add(node , val);
		return;
	}
	if(tree[node].lzy != 0)  Shift(node);
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	Add(l , r , val , lc , nl , mid);  Add(l , r , val , rc , mid , nr);
	tree[node] = Merge(tree[lc] , tree[rc]);
}

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);
	Build();
	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(st[v] , fn[v] , tmp);
		edges[id].S = val;
		last = tree[1].ans;
		cout << last << '\n';
	}
	return 0;
}

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