oj.uz

Submission #558542

# Submission time Handle Problem Language Result Execution time Memory
558542 2022-05-07T13:57:35 Z savacska Sprinkler (JOI22_sprinkler) C++17
53 / 100
 4000 ms 515920 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
const int MAXD = 40;
const int MAXN = 200000;
int MOD = 0;
 
vector <int> g[MAXN + 5];
int height[MAXN + 5], position[MAXN + 5], parent[MAXN + 5], start_height[MAXN + 5], rows[MAXN + 5];
pair <int, int> subtree[MAXD + 5][MAXN + 5];
vector <int> tree[MAXN + 5];
deque <pair <pair <int, int>, int> > ququ[MAXN + 5];
 
void dfs(int v, int pr, int hei)
{
	parent[v] = pr;
	height[v] = hei;
	position[v] = rows[hei];
	rows[hei]++;
 
	int pos = -1;
	for (int i = 0; i < (int) g[v].size(); i++)
		if (g[v][i] == pr) pos = i;
	if (pos != -1)
	{
	 	swap(g[v][pos], g[v].back());
	 	g[v].pop_back();
	}
 
	for (int u : g[v])
		dfs(u, v, hei + 1);
 
	subtree[0][v] = mp(position[v], position[v]);
	if (!g[v].empty())
	{
	 	subtree[1][v] = mp(position[g[v][0]], position[g[v].back()]);
	 	int lef = 0, rig = (int) g[v].size() - 1;
	 	for (int i = 2; i <= MAXD; i++)
	 	{
	 	 	while (lef <= rig && subtree[i - 1][g[v][lef]] == mp(-1, -1)) lef++;
	 	 	while (lef <= rig && subtree[i - 1][g[v][rig]] == mp(-1, -1)) rig--;
	 	 	if (lef <= rig) subtree[i][v] = mp(subtree[i - 1][g[v][lef]].x, subtree[i - 1][g[v][rig]].y);
	 	 	else break;
	 	}
	}
	return;
}
 
int get_height(vector <int> &tree, int v, int lef, int rig, int pos, int cur_val)
{
 	if (tree[v] != 1) cur_val = (ll) cur_val * (ll) tree[v] % (ll) MOD;
 	if (cur_val == 0) return 0;
 	if (lef == rig) return cur_val;
 	int mid = (lef + rig) / 2;
 	if (pos <= mid) return get_height(tree, 2 * v, lef, mid, pos, cur_val);
 	else return get_height(tree, 2 * v + 1, mid + 1, rig, pos, cur_val);
}
 
void update(vector <int> &tree, int v, int lef, int rig, int A, int B, int mn)
{
 	if (lef > B || rig < A) return;
 	if (A <= lef && rig <= B)
 	{
 	 	tree[v] = (ll) tree[v] * (ll) mn % (ll) MOD;
 	 	return;
 	}
 	int mid = (lef + rig) / 2;
 	if (tree[v] != 1)
 	{
 	 	tree[2 * v] = (ll) tree[2 * v] * (ll) tree[v] % (ll) MOD;
 	 	tree[2 * v + 1] = (ll) tree[2 * v + 1] * (ll) tree[v] % (ll) MOD;
 	 	tree[v] = 1;
 	}
 	update(tree, 2 * v, lef, mid, A, B, mn);
 	update(tree, 2 * v + 1, mid + 1, rig, A, B, mn);
 	return;
}
 
int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);
 	
 	int n, mod;
 	cin >> n >> mod;
 	MOD = mod;
 	
 	for (int i = 0; i <= MAXD; i++)
 		for (int j = 1; j <= n; j++)
 			subtree[i][j] = mp(-1, -1);
 
 	for (int i = 1; i < n; i++)
 	{
 	 	int u, v;
 	 	cin >> u >> v;
 	 	g[u].pb(v), g[v].pb(u);
 	}
 
 	for (int i = 1; i <= n; i++) cin >> start_height[i];
 
 	dfs(1, -1, 0);
 	
 	{
 	 	int h = 0;
 	 	while (rows[h] > 0)
 	 	{
 	 	 	tree[h].resize(4 * rows[h], 1);
 	 	 	h++;
 	 	}
 	}
 	
 	int quer;
 	cin >> quer;
 	
 	for (int rep = 1; rep <= quer; rep++)
 	{
 	 	int typ;
 	 	cin >> typ;
 	 	if (typ == 1)
 	 	{
 	 	 	int vert, dist, mn;
 	 	 	cin >> vert >> dist >> mn;
 
            int cur = 0, curv = vert;
 	 	 	for (int fin = height[vert] + dist; fin >= height[vert] - dist; fin--)
 	 	 	{
 	 	 	 	int x = (dist + height[vert] - fin) / 2;
 	 	 	 	if (x > cur)
 	 	 	 	{
 	 	 	 	 	if (parent[curv] != -1) curv = parent[curv], cur++;
 	 	 	 	} 
 	 	 	 	if (height[curv] > fin) break;
 
 	 	 	 	int y = fin - height[curv];
 	 	 	 	pair <int, int> bounds = subtree[y][curv];
 	 	 	 	if (bounds.x == -1) continue;
 	 	 	 	if (mn != 1) ququ[fin].pb(mp(mp(bounds.x, bounds.y), mn));
 	 	 	}
 	 	}
 	 	else
 	 	{
 	 		int vert;
 	 		cin >> vert;
 
            int heh = height[vert];
            while (!ququ[heh].empty())
            {
             	pair <pair <int, int>, int> A = ququ[heh].front();
             	ququ[heh].pop_front();
             	update(tree[heh], 1, 0, rows[heh] - 1, A.x.x, A.x.y, A.y);
            }
 	 		int ans = get_height(tree[heh], 1, 0, rows[heh] - 1, position[vert], 1);
 	 		ans = (ll) ans * (ll) start_height[vert] % (ll) MOD;
 	 		cout << ans << '\n';
 	 	}
 	}
 	return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 141512 KB Output is correct
2 Correct 82 ms 141424 KB Output is correct
3 Correct 85 ms 141480 KB Output is correct
4 Correct 92 ms 142044 KB Output is correct
5 Correct 86 ms 141888 KB Output is correct
6 Correct 91 ms 141964 KB Output is correct
7 Correct 88 ms 141900 KB Output is correct
8 Correct 100 ms 141864 KB Output is correct
9 Correct 102 ms 141452 KB Output is correct
10 Correct 83 ms 141480 KB Output is correct
11 Correct 82 ms 141500 KB Output is correct
12 Correct 80 ms 141484 KB Output is correct
13 Correct 86 ms 141532 KB Output is correct
14 Correct 86 ms 141484 KB Output is correct
15 Correct 82 ms 141432 KB Output is correct
16 Correct 81 ms 141536 KB Output is correct
17 Correct 83 ms 141460 KB Output is correct
18 Correct 82 ms 141436 KB Output is correct
19 Correct 87 ms 141432 KB Output is correct
20 Correct 94 ms 141400 KB Output is correct
21 Correct 83 ms 141528 KB Output is correct
22 Correct 85 ms 141412 KB Output is correct
23 Correct 83 ms 141516 KB Output is correct
24 Correct 87 ms 141460 KB Output is correct
25 Correct 99 ms 141532 KB Output is correct
26 Correct 87 ms 141436 KB Output is correct
27 Correct 83 ms 141536 KB Output is correct
28 Correct 82 ms 141516 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 141528 KB Output is correct
2 Correct 443 ms 221648 KB Output is correct
3 Correct 532 ms 218880 KB Output is correct
4 Correct 644 ms 234468 KB Output is correct
5 Correct 544 ms 220072 KB Output is correct
6 Correct 486 ms 219920 KB Output is correct
7 Correct 544 ms 220192 KB Output is correct
8 Correct 496 ms 221952 KB Output is correct
9 Correct 617 ms 243560 KB Output is correct
10 Correct 663 ms 238584 KB Output is correct
11 Correct 490 ms 221584 KB Output is correct
12 Correct 562 ms 218868 KB Output is correct
13 Correct 387 ms 226276 KB Output is correct
14 Correct 466 ms 223136 KB Output is correct
15 Correct 561 ms 220432 KB Output is correct
16 Correct 664 ms 219624 KB Output is correct
17 Correct 598 ms 219664 KB Output is correct
18 Correct 114 ms 141488 KB Output is correct
19 Correct 91 ms 141512 KB Output is correct
20 Correct 84 ms 141516 KB Output is correct
21 Correct 89 ms 141532 KB Output is correct
22 Correct 90 ms 141424 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 141528 KB Output is correct
2 Correct 443 ms 221648 KB Output is correct
3 Correct 532 ms 218880 KB Output is correct
4 Correct 644 ms 234468 KB Output is correct
5 Correct 544 ms 220072 KB Output is correct
6 Correct 486 ms 219920 KB Output is correct
7 Correct 544 ms 220192 KB Output is correct
8 Correct 496 ms 221952 KB Output is correct
9 Correct 617 ms 243560 KB Output is correct
10 Correct 663 ms 238584 KB Output is correct
11 Correct 490 ms 221584 KB Output is correct
12 Correct 562 ms 218868 KB Output is correct
13 Correct 387 ms 226276 KB Output is correct
14 Correct 466 ms 223136 KB Output is correct
15 Correct 561 ms 220432 KB Output is correct
16 Correct 664 ms 219624 KB Output is correct
17 Correct 598 ms 219664 KB Output is correct
18 Correct 114 ms 141488 KB Output is correct
19 Correct 91 ms 141512 KB Output is correct
20 Correct 84 ms 141516 KB Output is correct
21 Correct 89 ms 141532 KB Output is correct
22 Correct 90 ms 141424 KB Output is correct
23 Correct 90 ms 141516 KB Output is correct
24 Correct 507 ms 221620 KB Output is correct
25 Correct 815 ms 219076 KB Output is correct
26 Correct 712 ms 241108 KB Output is correct
27 Correct 644 ms 220196 KB Output is correct
28 Correct 579 ms 220292 KB Output is correct
29 Correct 592 ms 220156 KB Output is correct
30 Correct 436 ms 221904 KB Output is correct
31 Correct 615 ms 236812 KB Output is correct
32 Correct 711 ms 238576 KB Output is correct
33 Correct 520 ms 221616 KB Output is correct
34 Correct 695 ms 218876 KB Output is correct
35 Correct 86 ms 141524 KB Output is correct
36 Correct 84 ms 141444 KB Output is correct
37 Correct 83 ms 141524 KB Output is correct
38 Correct 88 ms 141516 KB Output is correct
39 Correct 86 ms 141528 KB Output is correct
40 Correct 81 ms 141404 KB Output is correct
41 Correct 83 ms 141432 KB Output is correct
42 Correct 82 ms 141516 KB Output is correct
43 Correct 93 ms 141476 KB Output is correct
44 Correct 103 ms 141520 KB Output is correct
45 Correct 81 ms 141532 KB Output is correct
46 Correct 82 ms 141496 KB Output is correct
47 Correct 84 ms 141532 KB Output is correct
48 Correct 86 ms 141532 KB Output is correct
49 Correct 90 ms 141476 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 141508 KB Output is correct
2 Correct 830 ms 240592 KB Output is correct
3 Correct 2702 ms 514696 KB Output is correct
4 Correct 1160 ms 275564 KB Output is correct
5 Correct 1604 ms 218960 KB Output is correct
6 Correct 1224 ms 220452 KB Output is correct
7 Correct 821 ms 222448 KB Output is correct
8 Correct 414 ms 223672 KB Output is correct
9 Correct 835 ms 235580 KB Output is correct
10 Correct 2591 ms 515920 KB Output is correct
11 Correct 904 ms 219112 KB Output is correct
12 Correct 3729 ms 230924 KB Output is correct
13 Correct 2609 ms 232012 KB Output is correct
14 Correct 1967 ms 245480 KB Output is correct
15 Correct 84 ms 141528 KB Output is correct
16 Correct 86 ms 141492 KB Output is correct
17 Correct 92 ms 141492 KB Output is correct
18 Correct 83 ms 141432 KB Output is correct
19 Correct 83 ms 141548 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 141496 KB Output is correct
2 Correct 875 ms 237400 KB Output is correct
3 Correct 2581 ms 513732 KB Output is correct
4 Correct 1174 ms 271312 KB Output is correct
5 Correct 1608 ms 220748 KB Output is correct
6 Correct 1246 ms 223680 KB Output is correct
7 Correct 918 ms 224456 KB Output is correct
8 Correct 497 ms 224152 KB Output is correct
9 Correct 866 ms 242508 KB Output is correct
10 Correct 2592 ms 515556 KB Output is correct
11 Correct 1018 ms 221752 KB Output is correct
12 Execution timed out 4086 ms 225772 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 141512 KB Output is correct
2 Correct 82 ms 141424 KB Output is correct
3 Correct 85 ms 141480 KB Output is correct
4 Correct 92 ms 142044 KB Output is correct
5 Correct 86 ms 141888 KB Output is correct
6 Correct 91 ms 141964 KB Output is correct
7 Correct 88 ms 141900 KB Output is correct
8 Correct 100 ms 141864 KB Output is correct
9 Correct 102 ms 141452 KB Output is correct
10 Correct 83 ms 141480 KB Output is correct
11 Correct 82 ms 141500 KB Output is correct
12 Correct 80 ms 141484 KB Output is correct
13 Correct 86 ms 141532 KB Output is correct
14 Correct 86 ms 141484 KB Output is correct
15 Correct 82 ms 141432 KB Output is correct
16 Correct 81 ms 141536 KB Output is correct
17 Correct 83 ms 141460 KB Output is correct
18 Correct 82 ms 141436 KB Output is correct
19 Correct 87 ms 141432 KB Output is correct
20 Correct 94 ms 141400 KB Output is correct
21 Correct 83 ms 141528 KB Output is correct
22 Correct 85 ms 141412 KB Output is correct
23 Correct 83 ms 141516 KB Output is correct
24 Correct 87 ms 141460 KB Output is correct
25 Correct 99 ms 141532 KB Output is correct
26 Correct 87 ms 141436 KB Output is correct
27 Correct 83 ms 141536 KB Output is correct
28 Correct 82 ms 141516 KB Output is correct
29 Correct 95 ms 141528 KB Output is correct
30 Correct 443 ms 221648 KB Output is correct
31 Correct 532 ms 218880 KB Output is correct
32 Correct 644 ms 234468 KB Output is correct
33 Correct 544 ms 220072 KB Output is correct
34 Correct 486 ms 219920 KB Output is correct
35 Correct 544 ms 220192 KB Output is correct
36 Correct 496 ms 221952 KB Output is correct
37 Correct 617 ms 243560 KB Output is correct
38 Correct 663 ms 238584 KB Output is correct
39 Correct 490 ms 221584 KB Output is correct
40 Correct 562 ms 218868 KB Output is correct
41 Correct 387 ms 226276 KB Output is correct
42 Correct 466 ms 223136 KB Output is correct
43 Correct 561 ms 220432 KB Output is correct
44 Correct 664 ms 219624 KB Output is correct
45 Correct 598 ms 219664 KB Output is correct
46 Correct 114 ms 141488 KB Output is correct
47 Correct 91 ms 141512 KB Output is correct
48 Correct 84 ms 141516 KB Output is correct
49 Correct 89 ms 141532 KB Output is correct
50 Correct 90 ms 141424 KB Output is correct
51 Correct 90 ms 141516 KB Output is correct
52 Correct 507 ms 221620 KB Output is correct
53 Correct 815 ms 219076 KB Output is correct
54 Correct 712 ms 241108 KB Output is correct
55 Correct 644 ms 220196 KB Output is correct
56 Correct 579 ms 220292 KB Output is correct
57 Correct 592 ms 220156 KB Output is correct
58 Correct 436 ms 221904 KB Output is correct
59 Correct 615 ms 236812 KB Output is correct
60 Correct 711 ms 238576 KB Output is correct
61 Correct 520 ms 221616 KB Output is correct
62 Correct 695 ms 218876 KB Output is correct
63 Correct 86 ms 141524 KB Output is correct
64 Correct 84 ms 141444 KB Output is correct
65 Correct 83 ms 141524 KB Output is correct
66 Correct 88 ms 141516 KB Output is correct
67 Correct 86 ms 141528 KB Output is correct
68 Correct 81 ms 141404 KB Output is correct
69 Correct 83 ms 141432 KB Output is correct
70 Correct 82 ms 141516 KB Output is correct
71 Correct 93 ms 141476 KB Output is correct
72 Correct 103 ms 141520 KB Output is correct
73 Correct 81 ms 141532 KB Output is correct
74 Correct 82 ms 141496 KB Output is correct
75 Correct 84 ms 141532 KB Output is correct
76 Correct 86 ms 141532 KB Output is correct
77 Correct 90 ms 141476 KB Output is correct
78 Correct 86 ms 141508 KB Output is correct
79 Correct 830 ms 240592 KB Output is correct
80 Correct 2702 ms 514696 KB Output is correct
81 Correct 1160 ms 275564 KB Output is correct
82 Correct 1604 ms 218960 KB Output is correct
83 Correct 1224 ms 220452 KB Output is correct
84 Correct 821 ms 222448 KB Output is correct
85 Correct 414 ms 223672 KB Output is correct
86 Correct 835 ms 235580 KB Output is correct
87 Correct 2591 ms 515920 KB Output is correct
88 Correct 904 ms 219112 KB Output is correct
89 Correct 3729 ms 230924 KB Output is correct
90 Correct 2609 ms 232012 KB Output is correct
91 Correct 1967 ms 245480 KB Output is correct
92 Correct 84 ms 141528 KB Output is correct
93 Correct 86 ms 141492 KB Output is correct
94 Correct 92 ms 141492 KB Output is correct
95 Correct 83 ms 141432 KB Output is correct
96 Correct 83 ms 141548 KB Output is correct
97 Correct 87 ms 141496 KB Output is correct
98 Correct 875 ms 237400 KB Output is correct
99 Correct 2581 ms 513732 KB Output is correct
100 Correct 1174 ms 271312 KB Output is correct
101 Correct 1608 ms 220748 KB Output is correct
102 Correct 1246 ms 223680 KB Output is correct
103 Correct 918 ms 224456 KB Output is correct
104 Correct 497 ms 224152 KB Output is correct
105 Correct 866 ms 242508 KB Output is correct
106 Correct 2592 ms 515556 KB Output is correct
107 Correct 1018 ms 221752 KB Output is correct
108 Execution timed out 4086 ms 225772 KB Time limit exceeded
109 Halted 0 ms 0 KB -