oj.uz

Submission #718632

# Submission time Handle Problem Language Result Execution time Memory
718632 2023-04-04T12:50:30 Z parsadox2 Dynamic Diameter (CEOI19_diameter) C++14
100 / 100
 462 ms 91508 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63756 KB Output is correct
2 Correct 26 ms 63732 KB Output is correct
3 Correct 26 ms 63704 KB Output is correct
4 Correct 23 ms 63700 KB Output is correct
5 Correct 25 ms 63764 KB Output is correct
6 Correct 26 ms 63696 KB Output is correct
7 Correct 24 ms 63768 KB Output is correct
8 Correct 30 ms 63652 KB Output is correct
9 Correct 26 ms 63664 KB Output is correct
10 Correct 28 ms 63732 KB Output is correct
11 Correct 25 ms 63716 KB Output is correct
12 Correct 27 ms 63640 KB Output is correct
13 Correct 25 ms 63700 KB Output is correct
14 Correct 24 ms 63696 KB Output is correct
15 Correct 25 ms 63712 KB Output is correct
16 Correct 23 ms 63688 KB Output is correct
17 Correct 26 ms 63692 KB Output is correct
18 Correct 25 ms 63692 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63756 KB Output is correct
2 Correct 26 ms 63732 KB Output is correct
3 Correct 26 ms 63704 KB Output is correct
4 Correct 23 ms 63700 KB Output is correct
5 Correct 25 ms 63764 KB Output is correct
6 Correct 26 ms 63696 KB Output is correct
7 Correct 24 ms 63768 KB Output is correct
8 Correct 30 ms 63652 KB Output is correct
9 Correct 26 ms 63664 KB Output is correct
10 Correct 28 ms 63732 KB Output is correct
11 Correct 25 ms 63716 KB Output is correct
12 Correct 27 ms 63640 KB Output is correct
13 Correct 25 ms 63700 KB Output is correct
14 Correct 24 ms 63696 KB Output is correct
15 Correct 25 ms 63712 KB Output is correct
16 Correct 23 ms 63688 KB Output is correct
17 Correct 26 ms 63692 KB Output is correct
18 Correct 25 ms 63692 KB Output is correct
19 Correct 31 ms 63864 KB Output is correct
20 Correct 30 ms 63892 KB Output is correct
21 Correct 31 ms 63928 KB Output is correct
22 Correct 29 ms 63956 KB Output is correct
23 Correct 32 ms 64492 KB Output is correct
24 Correct 31 ms 64460 KB Output is correct
25 Correct 30 ms 64548 KB Output is correct
26 Correct 32 ms 64960 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63700 KB Output is correct
2 Correct 27 ms 63692 KB Output is correct
3 Correct 28 ms 63700 KB Output is correct
4 Correct 31 ms 63752 KB Output is correct
5 Correct 62 ms 64076 KB Output is correct
6 Correct 25 ms 63736 KB Output is correct
7 Correct 26 ms 63744 KB Output is correct
8 Correct 29 ms 63692 KB Output is correct
9 Correct 26 ms 63796 KB Output is correct
10 Correct 35 ms 63820 KB Output is correct
11 Correct 74 ms 64216 KB Output is correct
12 Correct 26 ms 64468 KB Output is correct
13 Correct 26 ms 64468 KB Output is correct
14 Correct 31 ms 64512 KB Output is correct
15 Correct 43 ms 64588 KB Output is correct
16 Correct 95 ms 64940 KB Output is correct
17 Correct 67 ms 77500 KB Output is correct
18 Correct 66 ms 78640 KB Output is correct
19 Correct 68 ms 78736 KB Output is correct
20 Correct 84 ms 79020 KB Output is correct
21 Correct 228 ms 80340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 63820 KB Output is correct
2 Correct 36 ms 63944 KB Output is correct
3 Correct 60 ms 64080 KB Output is correct
4 Correct 119 ms 64440 KB Output is correct
5 Correct 33 ms 65160 KB Output is correct
6 Correct 41 ms 65288 KB Output is correct
7 Correct 79 ms 65560 KB Output is correct
8 Correct 124 ms 65880 KB Output is correct
9 Correct 49 ms 71040 KB Output is correct
10 Correct 79 ms 71140 KB Output is correct
11 Correct 122 ms 71324 KB Output is correct
12 Correct 177 ms 71624 KB Output is correct
13 Correct 71 ms 78236 KB Output is correct
14 Correct 87 ms 79992 KB Output is correct
15 Correct 148 ms 80612 KB Output is correct
16 Correct 208 ms 81752 KB Output is correct
17 Correct 191 ms 81284 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 81472 KB Output is correct
2 Correct 259 ms 83652 KB Output is correct
3 Correct 257 ms 83812 KB Output is correct
4 Correct 275 ms 83944 KB Output is correct
5 Correct 292 ms 83612 KB Output is correct
6 Correct 259 ms 83500 KB Output is correct
7 Correct 315 ms 86864 KB Output is correct
8 Correct 327 ms 86940 KB Output is correct
9 Correct 310 ms 86760 KB Output is correct
10 Correct 292 ms 86728 KB Output is correct
11 Correct 340 ms 86516 KB Output is correct
12 Correct 293 ms 85592 KB Output is correct
13 Correct 352 ms 91400 KB Output is correct
14 Correct 362 ms 91508 KB Output is correct
15 Correct 415 ms 91380 KB Output is correct
16 Correct 412 ms 91380 KB Output is correct
17 Correct 391 ms 90748 KB Output is correct
18 Correct 462 ms 87316 KB Output is correct
19 Correct 439 ms 91444 KB Output is correct
20 Correct 396 ms 91332 KB Output is correct
21 Correct 432 ms 91464 KB Output is correct
22 Correct 355 ms 91340 KB Output is correct
23 Correct 357 ms 90792 KB Output is correct
24 Correct 345 ms 87212 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63756 KB Output is correct
2 Correct 26 ms 63732 KB Output is correct
3 Correct 26 ms 63704 KB Output is correct
4 Correct 23 ms 63700 KB Output is correct
5 Correct 25 ms 63764 KB Output is correct
6 Correct 26 ms 63696 KB Output is correct
7 Correct 24 ms 63768 KB Output is correct
8 Correct 30 ms 63652 KB Output is correct
9 Correct 26 ms 63664 KB Output is correct
10 Correct 28 ms 63732 KB Output is correct
11 Correct 25 ms 63716 KB Output is correct
12 Correct 27 ms 63640 KB Output is correct
13 Correct 25 ms 63700 KB Output is correct
14 Correct 24 ms 63696 KB Output is correct
15 Correct 25 ms 63712 KB Output is correct
16 Correct 23 ms 63688 KB Output is correct
17 Correct 26 ms 63692 KB Output is correct
18 Correct 25 ms 63692 KB Output is correct
19 Correct 31 ms 63864 KB Output is correct
20 Correct 30 ms 63892 KB Output is correct
21 Correct 31 ms 63928 KB Output is correct
22 Correct 29 ms 63956 KB Output is correct
23 Correct 32 ms 64492 KB Output is correct
24 Correct 31 ms 64460 KB Output is correct
25 Correct 30 ms 64548 KB Output is correct
26 Correct 32 ms 64960 KB Output is correct
27 Correct 27 ms 63700 KB Output is correct
28 Correct 27 ms 63692 KB Output is correct
29 Correct 28 ms 63700 KB Output is correct
30 Correct 31 ms 63752 KB Output is correct
31 Correct 62 ms 64076 KB Output is correct
32 Correct 25 ms 63736 KB Output is correct
33 Correct 26 ms 63744 KB Output is correct
34 Correct 29 ms 63692 KB Output is correct
35 Correct 26 ms 63796 KB Output is correct
36 Correct 35 ms 63820 KB Output is correct
37 Correct 74 ms 64216 KB Output is correct
38 Correct 26 ms 64468 KB Output is correct
39 Correct 26 ms 64468 KB Output is correct
40 Correct 31 ms 64512 KB Output is correct
41 Correct 43 ms 64588 KB Output is correct
42 Correct 95 ms 64940 KB Output is correct
43 Correct 67 ms 77500 KB Output is correct
44 Correct 66 ms 78640 KB Output is correct
45 Correct 68 ms 78736 KB Output is correct
46 Correct 84 ms 79020 KB Output is correct
47 Correct 228 ms 80340 KB Output is correct
48 Correct 26 ms 63820 KB Output is correct
49 Correct 36 ms 63944 KB Output is correct
50 Correct 60 ms 64080 KB Output is correct
51 Correct 119 ms 64440 KB Output is correct
52 Correct 33 ms 65160 KB Output is correct
53 Correct 41 ms 65288 KB Output is correct
54 Correct 79 ms 65560 KB Output is correct
55 Correct 124 ms 65880 KB Output is correct
56 Correct 49 ms 71040 KB Output is correct
57 Correct 79 ms 71140 KB Output is correct
58 Correct 122 ms 71324 KB Output is correct
59 Correct 177 ms 71624 KB Output is correct
60 Correct 71 ms 78236 KB Output is correct
61 Correct 87 ms 79992 KB Output is correct
62 Correct 148 ms 80612 KB Output is correct
63 Correct 208 ms 81752 KB Output is correct
64 Correct 191 ms 81284 KB Output is correct
65 Correct 248 ms 81472 KB Output is correct
66 Correct 259 ms 83652 KB Output is correct
67 Correct 257 ms 83812 KB Output is correct
68 Correct 275 ms 83944 KB Output is correct
69 Correct 292 ms 83612 KB Output is correct
70 Correct 259 ms 83500 KB Output is correct
71 Correct 315 ms 86864 KB Output is correct
72 Correct 327 ms 86940 KB Output is correct
73 Correct 310 ms 86760 KB Output is correct
74 Correct 292 ms 86728 KB Output is correct
75 Correct 340 ms 86516 KB Output is correct
76 Correct 293 ms 85592 KB Output is correct
77 Correct 352 ms 91400 KB Output is correct
78 Correct 362 ms 91508 KB Output is correct
79 Correct 415 ms 91380 KB Output is correct
80 Correct 412 ms 91380 KB Output is correct
81 Correct 391 ms 90748 KB Output is correct
82 Correct 462 ms 87316 KB Output is correct
83 Correct 439 ms 91444 KB Output is correct
84 Correct 396 ms 91332 KB Output is correct
85 Correct 432 ms 91464 KB Output is correct
86 Correct 355 ms 91340 KB Output is correct
87 Correct 357 ms 90792 KB Output is correct
88 Correct 345 ms 87212 KB Output is correct
89 Correct 247 ms 82740 KB Output is correct
90 Correct 282 ms 83128 KB Output is correct
91 Correct 281 ms 84656 KB Output is correct
92 Correct 312 ms 84732 KB Output is correct
93 Correct 351 ms 87552 KB Output is correct
94 Correct 315 ms 86592 KB Output is correct
95 Correct 391 ms 88364 KB Output is correct
96 Correct 349 ms 87192 KB Output is correct
97 Correct 335 ms 88224 KB Output is correct
98 Correct 314 ms 90620 KB Output is correct
99 Correct 341 ms 88040 KB Output is correct
100 Correct 329 ms 87916 KB Output is correct