Submission #960479

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
960479	2024-04-10T14:06:25 Z	starchan	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	2457 ms	168112 KB

diameter

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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);
		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);
	vector<int> www(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++)
	{
		ANS.insert({0, 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]);
	}
	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

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

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	23384 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	23384 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	21376 KB	Output is correct
2	Correct	4 ms	21336 KB	Output is correct
3	Correct	5 ms	21388 KB	Output is correct
4	Correct	14 ms	21336 KB	Output is correct
5	Correct	52 ms	21764 KB	Output is correct
6	Correct	4 ms	21340 KB	Output is correct
7	Correct	4 ms	21620 KB	Output is correct
8	Correct	6 ms	21420 KB	Output is correct
9	Correct	6 ms	21596 KB	Output is correct
10	Correct	19 ms	21708 KB	Output is correct
11	Correct	76 ms	22068 KB	Output is correct
12	Correct	9 ms	24152 KB	Output is correct
13	Correct	9 ms	24156 KB	Output is correct
14	Correct	10 ms	24156 KB	Output is correct
15	Correct	30 ms	24304 KB	Output is correct
16	Correct	117 ms	24656 KB	Output is correct
17	Correct	111 ms	78276 KB	Output is correct
18	Correct	113 ms	78408 KB	Output is correct
19	Correct	117 ms	78392 KB	Output is correct
20	Correct	179 ms	78532 KB	Output is correct
21	Correct	338 ms	79084 KB	Output is correct