Submission #960530

#	Time	Username	Problem	Language	Result	Execution time	Memory
960530		starchan	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3530 ms	207036 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
struct seg_tree
{
	//range add range max.
	vector<int> tree, lazy;
	void init(int n)
	{
		tree.assign(4*n+2, 0);
		lazy.assign(4*n+2, 0);
		return;
	}
	void build(const vector<int> &a, int id, int l, int r)
	{
		int m = (l+r)/2;
		if(l==r)
		{
			tree[id] = a[m];
			return;
		}
		build(a, 2*id, l, m);
		build(a, 2*id+1, m+1, r);
		tree[id] = max(tree[2*id], tree[2*id+1]);
		return;
	}
	void upd(int val, int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return;
		if(ql <= l && r <= qr)
		{
			tree[id]+=val;
			lazy[id]+=val;
			return;
		}
		int m = (l+r)/2;
		upd(val, ql, qr, 2*id, l, m);
		upd(val, ql, qr, 2*id+1, m+1, r);
		tree[id] = max(tree[2*id], tree[2*id+1])+lazy[id];
		return;
	}
	int query(int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return 0;
		if(ql <= l && r <= qr)
			return tree[id];
		int m = (l+r)/2;
		int s1 = query(ql, qr, 2*id, l, m);
		int s2 = query(ql, qr, 2*id+1, m+1, r);
		return max(s1, s2);
	}
};
const int MX = 1e5+5;
const int LOGM = 17;
 
vector<in> adj[MX];
vector<seg_tree> work;
int pa[MX], tin[LOGM][MX], tout[LOGM][MX], just[LOGM][MX];
vector<pair<in, int>> edge;
vector<bool> cut(MX);
vector<int> sz(MX);
int centh[MX], ctin[MX], ctout[MX];
 
int ans[MX];//ans[i] stores max path through vertex i, where i has least centh[i]
set<in> ANS;//stores the above in a pair format (for efficient updates etc)
set<in> help[MX];//stores the neighbour set per centroid vertex with maximum weights enabled.
 
void dfs(int u, int p)
{
	sz[u] = 1;
	for(auto [v, w]: adj[u])
	{
		if(cut[v])
			continue;
		if(v==p)
			continue;
		dfs(v, u);
		sz[u]+=sz[v];
	}
	return;
}
 
int centroid(int u, int p, int SZ)
{
	for(auto [v, w]: adj[u])
	{
		if(cut[v])
			continue;
		if(v==p)
			continue;
		if(2*sz[v] > SZ)
			return centroid(v, u, SZ);
	}
	return u;
}
int centimer;
int centroid_decomposition(int u, int lvl)
{
	dfs(u, 0);
	int root = centroid(u, 0, sz[u]);
	work[root].init(sz[u]);
	cut[root] = 1; centh[root] = lvl; ctin[root] = ++centimer; sz[root] = sz[u];
	for(auto [v, w]: adj[root])
	{
		if(cut[v])
			continue;
		int X = centroid_decomposition(v, lvl+1);
		pa[X] = root;
	}
	ctout[root] = centimer;
	return root;
}
int cendfs(int u, int p, int root, int &timer, vector<int> &ref, int VALUE)
{
	int OPT = 0;
	ref.pb(VALUE);
	tin[centh[u]-centh[root]][u] = ++timer; 
	if((p != 0) && (p != root))
		just[centh[u]-centh[root]][u] = just[centh[p]-centh[root]][p];
	else
		just[centh[u]-centh[root]][u] = u;
	for(auto [v, w]: adj[u])
	{
		if(v==p)
			continue;
		if((ctin[v] < ctin[root]) || (ctout[v] > ctout[root]))
			continue;
		int WWW = cendfs(v, u, root, timer, ref, VALUE+w)+w;
		if(u == root)
			help[root].insert({WWW, v});
		OPT = max(OPT, WWW);
	}
	tout[centh[u]-centh[root]][u] = timer;
	return OPT;
}
void update(int root, int u, int val)
{
	int D = centh[u]-centh[root];
	int J = just[D][u];
	int D_p = centh[J]-centh[root];
	int NUM = work[root].query(tin[D_p][J], tout[D_p][J], 1, 1, sz[root]);
	help[root].erase({NUM, J});
	work[root].upd(val, tin[D][u], tout[D][u], 1, 1, sz[root]);
	NUM = work[root].query(tin[D_p][J], tout[D_p][J], 1, 1, sz[root]);
	help[root].insert({NUM, J});
	return;
}
 
int upd(int i, int val)
{
	auto [u, v] = edge[i].f;
	int delta = val-edge[i].s;
	edge[i] = {{u, v}, val};
	int root = (centh[u] < centh[v])? u : v;
	while(root)
	{
		if(tin[centh[u]-centh[root]][u] < tin[centh[v]-centh[root]][v])
			swap(u, v);
		update(root, u, delta);
		ANS.erase({ans[root], root});
		ans[root] = 0; auto it = help[root].end(); it--;
		ans[root]+=((*it).f); it--; ans[root]+=((*it).f);
		ANS.insert({ans[root], root});
		root = pa[root];
	}
	auto itt = ANS.end(); itt--;
	return (*itt).f;
}
signed main()
{
	fast();
	//freopen("out.txt", "w", stdout);
	int n, q, W;
	cin >> n >> q >> W;
	work.resize(n+1);
	int m = n-1;
	edge.resize(m);
	for(int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].pb({v, w}); adj[v].pb({u, w});
		edge[i] = {{u, v}, w};
	}
	int root = centroid_decomposition(1, 1);
	for(int i = 1; i <= n; i++)
	{
		help[i].insert({0, i});
		help[i].insert({0, 0});//ensuring there's always two elements: itself and fake zero.
	}
	for(int u = 1; u <= n; u++)
	{
		int timer = 0;
		vector<int> ref; ref.pb(0);
		cendfs(u, 0, u, timer, ref, 0);
		work[u].build(ref, 1, 1, sz[u]);
		ans[u] = 0; auto it = help[u].end(); it--; ans[u]+=((*it).f); it--; ans[u]+=((*it).f);
		ANS.insert({ans[u], u});
	}
	int lst = 0;
	while(q--)
	{
		int d, val;
		cin >> d >> val;
		d+=lst; d%=m; val+=lst; val%=W; lst = upd(d, val);
		cout << lst << "\n";
	}
	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:194:6: warning: unused variable 'root' [-Wunused-variable]
  194 |  int root = centroid_decomposition(1, 1);
      |      ^~~~

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