oj.uz

Submission #558532

# Submission time Handle Problem Language Result Execution time Memory
558532 2022-05-07T13:48:16 Z savacska Sprinkler (JOI22_sprinkler) C++17
83 / 100
 4000 ms 696548 KB 
#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];
vector <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 (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].back();
             	ququ[heh].pop_back();
             	update(tree[heh], 1, 0, rows[heh] - 1, A.x.x, A.x.y, A.y);
            }
 	 		int ans = get_height(tree[height[vert]], 1, 0, rows[height[vert]] - 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 8 ms 14676 KB Output is correct
2 Correct 7 ms 14736 KB Output is correct
3 Correct 7 ms 14620 KB Output is correct
4 Correct 9 ms 15444 KB Output is correct
5 Correct 9 ms 15188 KB Output is correct
6 Correct 8 ms 15128 KB Output is correct
7 Correct 9 ms 15188 KB Output is correct
8 Correct 10 ms 15108 KB Output is correct
9 Correct 9 ms 14676 KB Output is correct
10 Correct 8 ms 14640 KB Output is correct
11 Correct 7 ms 14676 KB Output is correct
12 Correct 8 ms 14676 KB Output is correct
13 Correct 8 ms 14676 KB Output is correct
14 Correct 8 ms 14648 KB Output is correct
15 Correct 8 ms 14724 KB Output is correct
16 Correct 8 ms 14676 KB Output is correct
17 Correct 8 ms 14676 KB Output is correct
18 Correct 9 ms 14676 KB Output is correct
19 Correct 8 ms 14676 KB Output is correct
20 Correct 8 ms 14676 KB Output is correct
21 Correct 8 ms 14676 KB Output is correct
22 Correct 9 ms 14676 KB Output is correct
23 Correct 8 ms 14676 KB Output is correct
24 Correct 8 ms 14696 KB Output is correct
25 Correct 8 ms 14676 KB Output is correct
26 Correct 9 ms 14676 KB Output is correct
27 Correct 8 ms 14676 KB Output is correct
28 Correct 8 ms 14676 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14676 KB Output is correct
2 Correct 353 ms 94924 KB Output is correct
3 Correct 458 ms 93396 KB Output is correct
4 Correct 538 ms 111948 KB Output is correct
5 Correct 407 ms 93520 KB Output is correct
6 Correct 400 ms 93044 KB Output is correct
7 Correct 397 ms 93428 KB Output is correct
8 Correct 335 ms 95824 KB Output is correct
9 Correct 511 ms 116584 KB Output is correct
10 Correct 636 ms 129228 KB Output is correct
11 Correct 347 ms 94924 KB Output is correct
12 Correct 455 ms 93668 KB Output is correct
13 Correct 293 ms 102684 KB Output is correct
14 Correct 392 ms 97736 KB Output is correct
15 Correct 429 ms 94236 KB Output is correct
16 Correct 435 ms 93240 KB Output is correct
17 Correct 487 ms 93056 KB Output is correct
18 Correct 8 ms 14676 KB Output is correct
19 Correct 8 ms 14704 KB Output is correct
20 Correct 8 ms 14676 KB Output is correct
21 Correct 8 ms 14676 KB Output is correct
22 Correct 9 ms 14676 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14676 KB Output is correct
2 Correct 353 ms 94924 KB Output is correct
3 Correct 458 ms 93396 KB Output is correct
4 Correct 538 ms 111948 KB Output is correct
5 Correct 407 ms 93520 KB Output is correct
6 Correct 400 ms 93044 KB Output is correct
7 Correct 397 ms 93428 KB Output is correct
8 Correct 335 ms 95824 KB Output is correct
9 Correct 511 ms 116584 KB Output is correct
10 Correct 636 ms 129228 KB Output is correct
11 Correct 347 ms 94924 KB Output is correct
12 Correct 455 ms 93668 KB Output is correct
13 Correct 293 ms 102684 KB Output is correct
14 Correct 392 ms 97736 KB Output is correct
15 Correct 429 ms 94236 KB Output is correct
16 Correct 435 ms 93240 KB Output is correct
17 Correct 487 ms 93056 KB Output is correct
18 Correct 8 ms 14676 KB Output is correct
19 Correct 8 ms 14704 KB Output is correct
20 Correct 8 ms 14676 KB Output is correct
21 Correct 8 ms 14676 KB Output is correct
22 Correct 9 ms 14676 KB Output is correct
23 Correct 8 ms 14732 KB Output is correct
24 Correct 372 ms 95012 KB Output is correct
25 Correct 523 ms 94548 KB Output is correct
26 Correct 593 ms 121480 KB Output is correct
27 Correct 436 ms 93644 KB Output is correct
28 Correct 455 ms 93316 KB Output is correct
29 Correct 454 ms 93308 KB Output is correct
30 Correct 362 ms 96252 KB Output is correct
31 Correct 518 ms 111408 KB Output is correct
32 Correct 750 ms 142852 KB Output is correct
33 Correct 437 ms 95160 KB Output is correct
34 Correct 617 ms 94300 KB Output is correct
35 Correct 7 ms 14676 KB Output is correct
36 Correct 8 ms 14676 KB Output is correct
37 Correct 8 ms 14744 KB Output is correct
38 Correct 8 ms 14744 KB Output is correct
39 Correct 8 ms 14676 KB Output is correct
40 Correct 9 ms 14736 KB Output is correct
41 Correct 8 ms 14676 KB Output is correct
42 Correct 9 ms 14676 KB Output is correct
43 Correct 8 ms 14676 KB Output is correct
44 Correct 8 ms 14676 KB Output is correct
45 Correct 8 ms 14740 KB Output is correct
46 Correct 8 ms 14748 KB Output is correct
47 Correct 10 ms 14660 KB Output is correct
48 Correct 9 ms 14676 KB Output is correct
49 Correct 8 ms 14676 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 982 ms 153804 KB Output is correct
3 Correct 2580 ms 667184 KB Output is correct
4 Correct 1234 ms 224308 KB Output is correct
5 Correct 1401 ms 94788 KB Output is correct
6 Correct 1172 ms 95380 KB Output is correct
7 Correct 717 ms 99052 KB Output is correct
8 Correct 336 ms 97952 KB Output is correct
9 Correct 850 ms 142172 KB Output is correct
10 Correct 2780 ms 692976 KB Output is correct
11 Correct 787 ms 93232 KB Output is correct
12 Correct 3226 ms 143508 KB Output is correct
13 Correct 2321 ms 152420 KB Output is correct
14 Correct 1573 ms 198168 KB Output is correct
15 Correct 8 ms 14676 KB Output is correct
16 Correct 10 ms 14680 KB Output is correct
17 Correct 8 ms 14676 KB Output is correct
18 Correct 9 ms 14688 KB Output is correct
19 Correct 8 ms 14688 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14676 KB Output is correct
2 Correct 915 ms 142820 KB Output is correct
3 Correct 2808 ms 676768 KB Output is correct
4 Correct 1194 ms 213720 KB Output is correct
5 Correct 1374 ms 97580 KB Output is correct
6 Correct 1086 ms 99508 KB Output is correct
7 Correct 803 ms 99472 KB Output is correct
8 Correct 334 ms 98520 KB Output is correct
9 Correct 922 ms 154668 KB Output is correct
10 Correct 2640 ms 696548 KB Output is correct
11 Correct 858 ms 95692 KB Output is correct
12 Correct 3842 ms 125212 KB Output is correct
13 Correct 2459 ms 148656 KB Output is correct
14 Correct 1639 ms 196988 KB Output is correct
15 Correct 8 ms 14676 KB Output is correct
16 Correct 9 ms 14684 KB Output is correct
17 Correct 8 ms 14684 KB Output is correct
18 Correct 8 ms 14676 KB Output is correct
19 Correct 8 ms 14676 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 7 ms 14736 KB Output is correct
3 Correct 7 ms 14620 KB Output is correct
4 Correct 9 ms 15444 KB Output is correct
5 Correct 9 ms 15188 KB Output is correct
6 Correct 8 ms 15128 KB Output is correct
7 Correct 9 ms 15188 KB Output is correct
8 Correct 10 ms 15108 KB Output is correct
9 Correct 9 ms 14676 KB Output is correct
10 Correct 8 ms 14640 KB Output is correct
11 Correct 7 ms 14676 KB Output is correct
12 Correct 8 ms 14676 KB Output is correct
13 Correct 8 ms 14676 KB Output is correct
14 Correct 8 ms 14648 KB Output is correct
15 Correct 8 ms 14724 KB Output is correct
16 Correct 8 ms 14676 KB Output is correct
17 Correct 8 ms 14676 KB Output is correct
18 Correct 9 ms 14676 KB Output is correct
19 Correct 8 ms 14676 KB Output is correct
20 Correct 8 ms 14676 KB Output is correct
21 Correct 8 ms 14676 KB Output is correct
22 Correct 9 ms 14676 KB Output is correct
23 Correct 8 ms 14676 KB Output is correct
24 Correct 8 ms 14696 KB Output is correct
25 Correct 8 ms 14676 KB Output is correct
26 Correct 9 ms 14676 KB Output is correct
27 Correct 8 ms 14676 KB Output is correct
28 Correct 8 ms 14676 KB Output is correct
29 Correct 7 ms 14676 KB Output is correct
30 Correct 353 ms 94924 KB Output is correct
31 Correct 458 ms 93396 KB Output is correct
32 Correct 538 ms 111948 KB Output is correct
33 Correct 407 ms 93520 KB Output is correct
34 Correct 400 ms 93044 KB Output is correct
35 Correct 397 ms 93428 KB Output is correct
36 Correct 335 ms 95824 KB Output is correct
37 Correct 511 ms 116584 KB Output is correct
38 Correct 636 ms 129228 KB Output is correct
39 Correct 347 ms 94924 KB Output is correct
40 Correct 455 ms 93668 KB Output is correct
41 Correct 293 ms 102684 KB Output is correct
42 Correct 392 ms 97736 KB Output is correct
43 Correct 429 ms 94236 KB Output is correct
44 Correct 435 ms 93240 KB Output is correct
45 Correct 487 ms 93056 KB Output is correct
46 Correct 8 ms 14676 KB Output is correct
47 Correct 8 ms 14704 KB Output is correct
48 Correct 8 ms 14676 KB Output is correct
49 Correct 8 ms 14676 KB Output is correct
50 Correct 9 ms 14676 KB Output is correct
51 Correct 8 ms 14732 KB Output is correct
52 Correct 372 ms 95012 KB Output is correct
53 Correct 523 ms 94548 KB Output is correct
54 Correct 593 ms 121480 KB Output is correct
55 Correct 436 ms 93644 KB Output is correct
56 Correct 455 ms 93316 KB Output is correct
57 Correct 454 ms 93308 KB Output is correct
58 Correct 362 ms 96252 KB Output is correct
59 Correct 518 ms 111408 KB Output is correct
60 Correct 750 ms 142852 KB Output is correct
61 Correct 437 ms 95160 KB Output is correct
62 Correct 617 ms 94300 KB Output is correct
63 Correct 7 ms 14676 KB Output is correct
64 Correct 8 ms 14676 KB Output is correct
65 Correct 8 ms 14744 KB Output is correct
66 Correct 8 ms 14744 KB Output is correct
67 Correct 8 ms 14676 KB Output is correct
68 Correct 9 ms 14736 KB Output is correct
69 Correct 8 ms 14676 KB Output is correct
70 Correct 9 ms 14676 KB Output is correct
71 Correct 8 ms 14676 KB Output is correct
72 Correct 8 ms 14676 KB Output is correct
73 Correct 8 ms 14740 KB Output is correct
74 Correct 8 ms 14748 KB Output is correct
75 Correct 10 ms 14660 KB Output is correct
76 Correct 9 ms 14676 KB Output is correct
77 Correct 8 ms 14676 KB Output is correct
78 Correct 8 ms 14676 KB Output is correct
79 Correct 982 ms 153804 KB Output is correct
80 Correct 2580 ms 667184 KB Output is correct
81 Correct 1234 ms 224308 KB Output is correct
82 Correct 1401 ms 94788 KB Output is correct
83 Correct 1172 ms 95380 KB Output is correct
84 Correct 717 ms 99052 KB Output is correct
85 Correct 336 ms 97952 KB Output is correct
86 Correct 850 ms 142172 KB Output is correct
87 Correct 2780 ms 692976 KB Output is correct
88 Correct 787 ms 93232 KB Output is correct
89 Correct 3226 ms 143508 KB Output is correct
90 Correct 2321 ms 152420 KB Output is correct
91 Correct 1573 ms 198168 KB Output is correct
92 Correct 8 ms 14676 KB Output is correct
93 Correct 10 ms 14680 KB Output is correct
94 Correct 8 ms 14676 KB Output is correct
95 Correct 9 ms 14688 KB Output is correct
96 Correct 8 ms 14688 KB Output is correct
97 Correct 7 ms 14676 KB Output is correct
98 Correct 915 ms 142820 KB Output is correct
99 Correct 2808 ms 676768 KB Output is correct
100 Correct 1194 ms 213720 KB Output is correct
101 Correct 1374 ms 97580 KB Output is correct
102 Correct 1086 ms 99508 KB Output is correct
103 Correct 803 ms 99472 KB Output is correct
104 Correct 334 ms 98520 KB Output is correct
105 Correct 922 ms 154668 KB Output is correct
106 Correct 2640 ms 696548 KB Output is correct
107 Correct 858 ms 95692 KB Output is correct
108 Correct 3842 ms 125212 KB Output is correct
109 Correct 2459 ms 148656 KB Output is correct
110 Correct 1639 ms 196988 KB Output is correct
111 Correct 8 ms 14676 KB Output is correct
112 Correct 9 ms 14684 KB Output is correct
113 Correct 8 ms 14684 KB Output is correct
114 Correct 8 ms 14676 KB Output is correct
115 Correct 8 ms 14676 KB Output is correct
116 Correct 811 ms 101676 KB Output is correct
117 Correct 3657 ms 140224 KB Output is correct
118 Correct 1290 ms 247432 KB Output is correct
119 Correct 1488 ms 105660 KB Output is correct
120 Correct 1234 ms 106632 KB Output is correct
121 Correct 944 ms 109028 KB Output is correct
122 Correct 353 ms 106832 KB Output is correct
123 Correct 908 ms 156560 KB Output is correct
124 Correct 3049 ms 681024 KB Output is correct
125 Correct 964 ms 101908 KB Output is correct
126 Execution timed out 4026 ms 138708 KB Time limit exceeded
127 Halted 0 ms 0 KB -