oj.uz

Submission #625288

# Submission time Handle Problem Language Result Execution time Memory
625288 2022-08-09T20:56:13 Z flappybird Sprinkler (JOI22_sprinkler) C++17
100 / 100
 824 ms 94656 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 202020
#define MAXS 41
#define INF 1000000000000000001
#define MOD 998244353
#define bb ' '
#define ln '\n'
#define Ln '\n'
ll L;
ll H[MAX];
ll mul[MAXS][MAX];
vector<int> adj[MAX];
int prt[MAX];
void dfs(int x, int p = 0) {
	prt[x] = p;
	for (auto v : adj[x]) if (v != p) dfs(v, x);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N >> L;
	int i, a, b;
	for (i = 1; i < N; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (i = 1; i <= N; i++) cin >> H[i];
	for (i = 1; i <= N; i++) for (int j = 0; j < MAXS; j++) mul[j][i] = 1;
	dfs(1);
	int Q;
	cin >> Q;
	while (Q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int X, D;
			ll W;
			cin >> X >> D >> W;
			if (D == 0) H[X] *= W, H[X] %= L;
			else {
				int v = X;
				while (1) {
					if (v == 1) {
						for (int k = 0; k <= D; k++) mul[k][v] *= W, mul[k][v] %= L;
						break;
					}
					else {
						if (!D) {
							H[v] *= W;
							H[v] %= L;
							break;
						}
						for (int k = D - 1; k <= D; k++) mul[k][v] *= W, mul[k][v] %= L;
						D--;
						v = prt[v];
					}
				}
			}
		}
		else {
			int v;
			cin >> v;
			int dis = 0;
			ll ans = H[v];
			int x = v;
			while (1) {
				if (dis > 40) break;
				if (!x) break;
				ans *= mul[dis][x];
				ans %= L;
				dis++;
				x = prt[x];
			}
			cout << ans << ln;
		}
	}
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 4 ms 5332 KB Output is correct
3 Correct 3 ms 5336 KB Output is correct
4 Correct 4 ms 5716 KB Output is correct
5 Correct 4 ms 5716 KB Output is correct
6 Correct 4 ms 5656 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 3 ms 5736 KB Output is correct
9 Correct 4 ms 5332 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 3 ms 5332 KB Output is correct
12 Correct 3 ms 5348 KB Output is correct
13 Correct 3 ms 5332 KB Output is correct
14 Correct 3 ms 5332 KB Output is correct
15 Correct 3 ms 5332 KB Output is correct
16 Correct 3 ms 5332 KB Output is correct
17 Correct 3 ms 5332 KB Output is correct
18 Correct 3 ms 5332 KB Output is correct
19 Correct 3 ms 5336 KB Output is correct
20 Correct 3 ms 5332 KB Output is correct
21 Correct 3 ms 5340 KB Output is correct
22 Correct 3 ms 5344 KB Output is correct
23 Correct 3 ms 5332 KB Output is correct
24 Correct 3 ms 5332 KB Output is correct
25 Correct 3 ms 5340 KB Output is correct
26 Correct 3 ms 5332 KB Output is correct
27 Correct 4 ms 5332 KB Output is correct
28 Correct 3 ms 5332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 508 ms 89896 KB Output is correct
3 Correct 335 ms 90460 KB Output is correct
4 Correct 435 ms 93004 KB Output is correct
5 Correct 454 ms 90112 KB Output is correct
6 Correct 348 ms 89776 KB Output is correct
7 Correct 295 ms 90420 KB Output is correct
8 Correct 328 ms 90868 KB Output is correct
9 Correct 541 ms 94420 KB Output is correct
10 Correct 361 ms 94656 KB Output is correct
11 Correct 516 ms 89892 KB Output is correct
12 Correct 353 ms 90260 KB Output is correct
13 Correct 242 ms 90704 KB Output is correct
14 Correct 228 ms 91076 KB Output is correct
15 Correct 239 ms 90548 KB Output is correct
16 Correct 263 ms 91028 KB Output is correct
17 Correct 254 ms 91532 KB Output is correct
18 Correct 4 ms 5332 KB Output is correct
19 Correct 4 ms 5324 KB Output is correct
20 Correct 3 ms 5332 KB Output is correct
21 Correct 3 ms 5332 KB Output is correct
22 Correct 3 ms 5332 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 508 ms 89896 KB Output is correct
3 Correct 335 ms 90460 KB Output is correct
4 Correct 435 ms 93004 KB Output is correct
5 Correct 454 ms 90112 KB Output is correct
6 Correct 348 ms 89776 KB Output is correct
7 Correct 295 ms 90420 KB Output is correct
8 Correct 328 ms 90868 KB Output is correct
9 Correct 541 ms 94420 KB Output is correct
10 Correct 361 ms 94656 KB Output is correct
11 Correct 516 ms 89892 KB Output is correct
12 Correct 353 ms 90260 KB Output is correct
13 Correct 242 ms 90704 KB Output is correct
14 Correct 228 ms 91076 KB Output is correct
15 Correct 239 ms 90548 KB Output is correct
16 Correct 263 ms 91028 KB Output is correct
17 Correct 254 ms 91532 KB Output is correct
18 Correct 4 ms 5332 KB Output is correct
19 Correct 4 ms 5324 KB Output is correct
20 Correct 3 ms 5332 KB Output is correct
21 Correct 3 ms 5332 KB Output is correct
22 Correct 3 ms 5332 KB Output is correct
23 Correct 3 ms 5340 KB Output is correct
24 Correct 534 ms 89924 KB Output is correct
25 Correct 328 ms 90308 KB Output is correct
26 Correct 447 ms 94560 KB Output is correct
27 Correct 431 ms 90044 KB Output is correct
28 Correct 344 ms 90316 KB Output is correct
29 Correct 300 ms 89956 KB Output is correct
30 Correct 262 ms 91088 KB Output is correct
31 Correct 544 ms 93016 KB Output is correct
32 Correct 391 ms 94564 KB Output is correct
33 Correct 539 ms 89784 KB Output is correct
34 Correct 333 ms 90288 KB Output is correct
35 Correct 3 ms 5332 KB Output is correct
36 Correct 3 ms 5332 KB Output is correct
37 Correct 3 ms 5332 KB Output is correct
38 Correct 3 ms 5332 KB Output is correct
39 Correct 3 ms 5332 KB Output is correct
40 Correct 3 ms 5332 KB Output is correct
41 Correct 3 ms 5332 KB Output is correct
42 Correct 3 ms 5332 KB Output is correct
43 Correct 4 ms 5332 KB Output is correct
44 Correct 3 ms 5332 KB Output is correct
45 Correct 3 ms 5332 KB Output is correct
46 Correct 3 ms 5332 KB Output is correct
47 Correct 4 ms 5332 KB Output is correct
48 Correct 3 ms 5332 KB Output is correct
49 Correct 3 ms 5332 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5332 KB Output is correct
2 Correct 591 ms 91592 KB Output is correct
3 Correct 696 ms 91036 KB Output is correct
4 Correct 540 ms 90764 KB Output is correct
5 Correct 603 ms 87080 KB Output is correct
6 Correct 361 ms 87324 KB Output is correct
7 Correct 333 ms 87412 KB Output is correct
8 Correct 239 ms 87868 KB Output is correct
9 Correct 607 ms 90072 KB Output is correct
10 Correct 749 ms 91656 KB Output is correct
11 Correct 535 ms 86788 KB Output is correct
12 Correct 735 ms 87644 KB Output is correct
13 Correct 527 ms 88532 KB Output is correct
14 Correct 588 ms 89056 KB Output is correct
15 Correct 3 ms 5332 KB Output is correct
16 Correct 3 ms 5332 KB Output is correct
17 Correct 3 ms 5332 KB Output is correct
18 Correct 3 ms 5332 KB Output is correct
19 Correct 4 ms 5340 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 602 ms 92520 KB Output is correct
3 Correct 735 ms 90288 KB Output is correct
4 Correct 543 ms 91296 KB Output is correct
5 Correct 503 ms 88780 KB Output is correct
6 Correct 387 ms 88816 KB Output is correct
7 Correct 349 ms 88636 KB Output is correct
8 Correct 239 ms 88908 KB Output is correct
9 Correct 576 ms 93848 KB Output is correct
10 Correct 743 ms 92292 KB Output is correct
11 Correct 535 ms 89412 KB Output is correct
12 Correct 745 ms 87980 KB Output is correct
13 Correct 506 ms 88652 KB Output is correct
14 Correct 565 ms 89268 KB Output is correct
15 Correct 3 ms 5332 KB Output is correct
16 Correct 3 ms 5340 KB Output is correct
17 Correct 3 ms 5332 KB Output is correct
18 Correct 5 ms 5312 KB Output is correct
19 Correct 3 ms 5332 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 4 ms 5332 KB Output is correct
3 Correct 3 ms 5336 KB Output is correct
4 Correct 4 ms 5716 KB Output is correct
5 Correct 4 ms 5716 KB Output is correct
6 Correct 4 ms 5656 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 3 ms 5736 KB Output is correct
9 Correct 4 ms 5332 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 3 ms 5332 KB Output is correct
12 Correct 3 ms 5348 KB Output is correct
13 Correct 3 ms 5332 KB Output is correct
14 Correct 3 ms 5332 KB Output is correct
15 Correct 3 ms 5332 KB Output is correct
16 Correct 3 ms 5332 KB Output is correct
17 Correct 3 ms 5332 KB Output is correct
18 Correct 3 ms 5332 KB Output is correct
19 Correct 3 ms 5336 KB Output is correct
20 Correct 3 ms 5332 KB Output is correct
21 Correct 3 ms 5340 KB Output is correct
22 Correct 3 ms 5344 KB Output is correct
23 Correct 3 ms 5332 KB Output is correct
24 Correct 3 ms 5332 KB Output is correct
25 Correct 3 ms 5340 KB Output is correct
26 Correct 3 ms 5332 KB Output is correct
27 Correct 4 ms 5332 KB Output is correct
28 Correct 3 ms 5332 KB Output is correct
29 Correct 3 ms 5332 KB Output is correct
30 Correct 508 ms 89896 KB Output is correct
31 Correct 335 ms 90460 KB Output is correct
32 Correct 435 ms 93004 KB Output is correct
33 Correct 454 ms 90112 KB Output is correct
34 Correct 348 ms 89776 KB Output is correct
35 Correct 295 ms 90420 KB Output is correct
36 Correct 328 ms 90868 KB Output is correct
37 Correct 541 ms 94420 KB Output is correct
38 Correct 361 ms 94656 KB Output is correct
39 Correct 516 ms 89892 KB Output is correct
40 Correct 353 ms 90260 KB Output is correct
41 Correct 242 ms 90704 KB Output is correct
42 Correct 228 ms 91076 KB Output is correct
43 Correct 239 ms 90548 KB Output is correct
44 Correct 263 ms 91028 KB Output is correct
45 Correct 254 ms 91532 KB Output is correct
46 Correct 4 ms 5332 KB Output is correct
47 Correct 4 ms 5324 KB Output is correct
48 Correct 3 ms 5332 KB Output is correct
49 Correct 3 ms 5332 KB Output is correct
50 Correct 3 ms 5332 KB Output is correct
51 Correct 3 ms 5340 KB Output is correct
52 Correct 534 ms 89924 KB Output is correct
53 Correct 328 ms 90308 KB Output is correct
54 Correct 447 ms 94560 KB Output is correct
55 Correct 431 ms 90044 KB Output is correct
56 Correct 344 ms 90316 KB Output is correct
57 Correct 300 ms 89956 KB Output is correct
58 Correct 262 ms 91088 KB Output is correct
59 Correct 544 ms 93016 KB Output is correct
60 Correct 391 ms 94564 KB Output is correct
61 Correct 539 ms 89784 KB Output is correct
62 Correct 333 ms 90288 KB Output is correct
63 Correct 3 ms 5332 KB Output is correct
64 Correct 3 ms 5332 KB Output is correct
65 Correct 3 ms 5332 KB Output is correct
66 Correct 3 ms 5332 KB Output is correct
67 Correct 3 ms 5332 KB Output is correct
68 Correct 3 ms 5332 KB Output is correct
69 Correct 3 ms 5332 KB Output is correct
70 Correct 3 ms 5332 KB Output is correct
71 Correct 4 ms 5332 KB Output is correct
72 Correct 3 ms 5332 KB Output is correct
73 Correct 3 ms 5332 KB Output is correct
74 Correct 3 ms 5332 KB Output is correct
75 Correct 4 ms 5332 KB Output is correct
76 Correct 3 ms 5332 KB Output is correct
77 Correct 3 ms 5332 KB Output is correct
78 Correct 2 ms 5332 KB Output is correct
79 Correct 591 ms 91592 KB Output is correct
80 Correct 696 ms 91036 KB Output is correct
81 Correct 540 ms 90764 KB Output is correct
82 Correct 603 ms 87080 KB Output is correct
83 Correct 361 ms 87324 KB Output is correct
84 Correct 333 ms 87412 KB Output is correct
85 Correct 239 ms 87868 KB Output is correct
86 Correct 607 ms 90072 KB Output is correct
87 Correct 749 ms 91656 KB Output is correct
88 Correct 535 ms 86788 KB Output is correct
89 Correct 735 ms 87644 KB Output is correct
90 Correct 527 ms 88532 KB Output is correct
91 Correct 588 ms 89056 KB Output is correct
92 Correct 3 ms 5332 KB Output is correct
93 Correct 3 ms 5332 KB Output is correct
94 Correct 3 ms 5332 KB Output is correct
95 Correct 3 ms 5332 KB Output is correct
96 Correct 4 ms 5340 KB Output is correct
97 Correct 3 ms 5332 KB Output is correct
98 Correct 602 ms 92520 KB Output is correct
99 Correct 735 ms 90288 KB Output is correct
100 Correct 543 ms 91296 KB Output is correct
101 Correct 503 ms 88780 KB Output is correct
102 Correct 387 ms 88816 KB Output is correct
103 Correct 349 ms 88636 KB Output is correct
104 Correct 239 ms 88908 KB Output is correct
105 Correct 576 ms 93848 KB Output is correct
106 Correct 743 ms 92292 KB Output is correct
107 Correct 535 ms 89412 KB Output is correct
108 Correct 745 ms 87980 KB Output is correct
109 Correct 506 ms 88652 KB Output is correct
110 Correct 565 ms 89268 KB Output is correct
111 Correct 3 ms 5332 KB Output is correct
112 Correct 3 ms 5340 KB Output is correct
113 Correct 3 ms 5332 KB Output is correct
114 Correct 5 ms 5312 KB Output is correct
115 Correct 3 ms 5332 KB Output is correct
116 Correct 530 ms 87896 KB Output is correct
117 Correct 727 ms 90396 KB Output is correct
118 Correct 555 ms 94408 KB Output is correct
119 Correct 532 ms 90120 KB Output is correct
120 Correct 387 ms 89688 KB Output is correct
121 Correct 419 ms 90584 KB Output is correct
122 Correct 306 ms 90860 KB Output is correct
123 Correct 584 ms 93600 KB Output is correct
124 Correct 749 ms 92968 KB Output is correct
125 Correct 555 ms 89064 KB Output is correct
126 Correct 722 ms 90400 KB Output is correct
127 Correct 824 ms 90824 KB Output is correct
128 Correct 595 ms 91556 KB Output is correct
129 Correct 562 ms 91984 KB Output is correct