oj.uz

Submission #960529

# Submission time Handle Problem Language Result Execution time Memory
960529 2024-04-10T15:23:37 Z starchan Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 3504 ms 209508 KB 
#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);
		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

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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23388 KB Output is correct
2 Correct 5 ms 23388 KB Output is correct
3 Correct 4 ms 23388 KB Output is correct
4 Correct 4 ms 23388 KB Output is correct
5 Correct 5 ms 23384 KB Output is correct
6 Correct 4 ms 23388 KB Output is correct
7 Correct 5 ms 27484 KB Output is correct
8 Correct 5 ms 29532 KB Output is correct
9 Correct 5 ms 29532 KB Output is correct
10 Correct 6 ms 29528 KB Output is correct
11 Correct 5 ms 29532 KB Output is correct
12 Correct 5 ms 29532 KB Output is correct
13 Correct 6 ms 29604 KB Output is correct
14 Correct 5 ms 29532 KB Output is correct
15 Correct 5 ms 29532 KB Output is correct
16 Correct 5 ms 29532 KB Output is correct
17 Correct 6 ms 33628 KB Output is correct
18 Correct 6 ms 33628 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23388 KB Output is correct
2 Correct 5 ms 23388 KB Output is correct
3 Correct 4 ms 23388 KB Output is correct
4 Correct 4 ms 23388 KB Output is correct
5 Correct 5 ms 23384 KB Output is correct
6 Correct 4 ms 23388 KB Output is correct
7 Correct 5 ms 27484 KB Output is correct
8 Correct 5 ms 29532 KB Output is correct
9 Correct 5 ms 29532 KB Output is correct
10 Correct 6 ms 29528 KB Output is correct
11 Correct 5 ms 29532 KB Output is correct
12 Correct 5 ms 29532 KB Output is correct
13 Correct 6 ms 29604 KB Output is correct
14 Correct 5 ms 29532 KB Output is correct
15 Correct 5 ms 29532 KB Output is correct
16 Correct 5 ms 29532 KB Output is correct
17 Correct 6 ms 33628 KB Output is correct
18 Correct 6 ms 33628 KB Output is correct
19 Correct 21 ms 36444 KB Output is correct
20 Correct 25 ms 40536 KB Output is correct
21 Correct 30 ms 40540 KB Output is correct
22 Correct 26 ms 40860 KB Output is correct
23 Correct 34 ms 43920 KB Output is correct
24 Correct 42 ms 46684 KB Output is correct
25 Correct 51 ms 51392 KB Output is correct
26 Correct 48 ms 52060 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21336 KB Output is correct
2 Correct 5 ms 21340 KB Output is correct
3 Correct 5 ms 21340 KB Output is correct
4 Correct 15 ms 21340 KB Output is correct
5 Correct 54 ms 21696 KB Output is correct
6 Correct 4 ms 21340 KB Output is correct
7 Correct 4 ms 21596 KB Output is correct
8 Correct 5 ms 21596 KB Output is correct
9 Correct 7 ms 21484 KB Output is correct
10 Correct 23 ms 21640 KB Output is correct
11 Correct 78 ms 22056 KB Output is correct
12 Correct 9 ms 24152 KB Output is correct
13 Correct 9 ms 23900 KB Output is correct
14 Correct 11 ms 24156 KB Output is correct
15 Correct 34 ms 24156 KB Output is correct
16 Correct 106 ms 24620 KB Output is correct
17 Correct 120 ms 76848 KB Output is correct
18 Correct 113 ms 76824 KB Output is correct
19 Correct 115 ms 76944 KB Output is correct
20 Correct 158 ms 76996 KB Output is correct
21 Correct 356 ms 77420 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 36440 KB Output is correct
2 Correct 28 ms 36700 KB Output is correct
3 Correct 114 ms 36796 KB Output is correct
4 Correct 217 ms 37040 KB Output is correct
5 Correct 30 ms 57356 KB Output is correct
6 Correct 58 ms 57560 KB Output is correct
7 Correct 212 ms 57600 KB Output is correct
8 Correct 392 ms 58168 KB Output is correct
9 Correct 105 ms 117148 KB Output is correct
10 Correct 169 ms 117188 KB Output is correct
11 Correct 427 ms 117260 KB Output is correct
12 Correct 801 ms 117696 KB Output is correct
13 Correct 222 ms 188340 KB Output is correct
14 Correct 305 ms 188468 KB Output is correct
15 Correct 674 ms 188852 KB Output is correct
16 Correct 1104 ms 189020 KB Output is correct
17 Correct 2416 ms 189180 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2330 ms 165664 KB Output is correct
2 Correct 2423 ms 167836 KB Output is correct
3 Correct 2393 ms 167388 KB Output is correct
4 Correct 2383 ms 167876 KB Output is correct
5 Correct 2322 ms 163120 KB Output is correct
6 Correct 2098 ms 139696 KB Output is correct
7 Correct 3152 ms 192964 KB Output is correct
8 Correct 3155 ms 196852 KB Output is correct
9 Correct 3171 ms 197132 KB Output is correct
10 Correct 3184 ms 196708 KB Output is correct
11 Correct 3003 ms 190240 KB Output is correct
12 Correct 2832 ms 159048 KB Output is correct
13 Correct 3374 ms 209312 KB Output is correct
14 Correct 3205 ms 208984 KB Output is correct
15 Correct 3292 ms 209508 KB Output is correct
16 Correct 3436 ms 208348 KB Output is correct
17 Correct 3284 ms 201708 KB Output is correct
18 Correct 2868 ms 164836 KB Output is correct
19 Correct 3468 ms 208916 KB Output is correct
20 Correct 3475 ms 209048 KB Output is correct
21 Correct 3483 ms 209116 KB Output is correct
22 Correct 3504 ms 209040 KB Output is correct
23 Correct 3400 ms 201192 KB Output is correct
24 Correct 2913 ms 165352 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23388 KB Output is correct
2 Correct 5 ms 23388 KB Output is correct
3 Correct 4 ms 23388 KB Output is correct
4 Correct 4 ms 23388 KB Output is correct
5 Correct 5 ms 23384 KB Output is correct
6 Correct 4 ms 23388 KB Output is correct
7 Correct 5 ms 27484 KB Output is correct
8 Correct 5 ms 29532 KB Output is correct
9 Correct 5 ms 29532 KB Output is correct
10 Correct 6 ms 29528 KB Output is correct
11 Correct 5 ms 29532 KB Output is correct
12 Correct 5 ms 29532 KB Output is correct
13 Correct 6 ms 29604 KB Output is correct
14 Correct 5 ms 29532 KB Output is correct
15 Correct 5 ms 29532 KB Output is correct
16 Correct 5 ms 29532 KB Output is correct
17 Correct 6 ms 33628 KB Output is correct
18 Correct 6 ms 33628 KB Output is correct
19 Correct 21 ms 36444 KB Output is correct
20 Correct 25 ms 40536 KB Output is correct
21 Correct 30 ms 40540 KB Output is correct
22 Correct 26 ms 40860 KB Output is correct
23 Correct 34 ms 43920 KB Output is correct
24 Correct 42 ms 46684 KB Output is correct
25 Correct 51 ms 51392 KB Output is correct
26 Correct 48 ms 52060 KB Output is correct
27 Correct 4 ms 21336 KB Output is correct
28 Correct 5 ms 21340 KB Output is correct
29 Correct 5 ms 21340 KB Output is correct
30 Correct 15 ms 21340 KB Output is correct
31 Correct 54 ms 21696 KB Output is correct
32 Correct 4 ms 21340 KB Output is correct
33 Correct 4 ms 21596 KB Output is correct
34 Correct 5 ms 21596 KB Output is correct
35 Correct 7 ms 21484 KB Output is correct
36 Correct 23 ms 21640 KB Output is correct
37 Correct 78 ms 22056 KB Output is correct
38 Correct 9 ms 24152 KB Output is correct
39 Correct 9 ms 23900 KB Output is correct
40 Correct 11 ms 24156 KB Output is correct
41 Correct 34 ms 24156 KB Output is correct
42 Correct 106 ms 24620 KB Output is correct
43 Correct 120 ms 76848 KB Output is correct
44 Correct 113 ms 76824 KB Output is correct
45 Correct 115 ms 76944 KB Output is correct
46 Correct 158 ms 76996 KB Output is correct
47 Correct 356 ms 77420 KB Output is correct
48 Correct 9 ms 36440 KB Output is correct
49 Correct 28 ms 36700 KB Output is correct
50 Correct 114 ms 36796 KB Output is correct
51 Correct 217 ms 37040 KB Output is correct
52 Correct 30 ms 57356 KB Output is correct
53 Correct 58 ms 57560 KB Output is correct
54 Correct 212 ms 57600 KB Output is correct
55 Correct 392 ms 58168 KB Output is correct
56 Correct 105 ms 117148 KB Output is correct
57 Correct 169 ms 117188 KB Output is correct
58 Correct 427 ms 117260 KB Output is correct
59 Correct 801 ms 117696 KB Output is correct
60 Correct 222 ms 188340 KB Output is correct
61 Correct 305 ms 188468 KB Output is correct
62 Correct 674 ms 188852 KB Output is correct
63 Correct 1104 ms 189020 KB Output is correct
64 Correct 2416 ms 189180 KB Output is correct
65 Correct 2330 ms 165664 KB Output is correct
66 Correct 2423 ms 167836 KB Output is correct
67 Correct 2393 ms 167388 KB Output is correct
68 Correct 2383 ms 167876 KB Output is correct
69 Correct 2322 ms 163120 KB Output is correct
70 Correct 2098 ms 139696 KB Output is correct
71 Correct 3152 ms 192964 KB Output is correct
72 Correct 3155 ms 196852 KB Output is correct
73 Correct 3171 ms 197132 KB Output is correct
74 Correct 3184 ms 196708 KB Output is correct
75 Correct 3003 ms 190240 KB Output is correct
76 Correct 2832 ms 159048 KB Output is correct
77 Correct 3374 ms 209312 KB Output is correct
78 Correct 3205 ms 208984 KB Output is correct
79 Correct 3292 ms 209508 KB Output is correct
80 Correct 3436 ms 208348 KB Output is correct
81 Correct 3284 ms 201708 KB Output is correct
82 Correct 2868 ms 164836 KB Output is correct
83 Correct 3468 ms 208916 KB Output is correct
84 Correct 3475 ms 209048 KB Output is correct
85 Correct 3483 ms 209116 KB Output is correct
86 Correct 3504 ms 209040 KB Output is correct
87 Correct 3400 ms 201192 KB Output is correct
88 Correct 2913 ms 165352 KB Output is correct
89 Correct 2416 ms 169784 KB Output is correct
90 Correct 2675 ms 179832 KB Output is correct
91 Correct 3146 ms 192880 KB Output is correct
92 Correct 3347 ms 196296 KB Output is correct
93 Correct 3434 ms 200940 KB Output is correct
94 Correct 3277 ms 204528 KB Output is correct
95 Correct 3328 ms 207520 KB Output is correct
96 Correct 3419 ms 207884 KB Output is correct
97 Correct 3336 ms 207308 KB Output is correct
98 Correct 3280 ms 208516 KB Output is correct
99 Correct 3480 ms 207724 KB Output is correct
100 Correct 3436 ms 207144 KB Output is correct