oj.uz

Submission #589276

# Submission time Handle Problem Language Result Execution time Memory
589276 2022-07-04T11:35:13 Z LastRonin Sprinkler (JOI22_sprinkler) C++14
100 / 100
 764 ms 79160 KB 
#pragma GCC optimize("O3")
 
#include <bits/stdc++.h> 
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
const int N = 2e5 + 60;
const int M = 5E5 + 100;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;
 
mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());
 
ll n, L, q, gl[N];
vector<int> g[N];
int dp[N];
int p[N], h[N];
int pr[N][41];

int mul(ll a, ll b) {	
	const ll z = L;
	return a * b % z;
}

void dfs(ll v, ll pr) {
	p[v] = pr;
	for(auto u : g[v]) {
		if(u == pr)continue;
		dfs(u, v);
	}

}

ll ans[M];
                        
ll t[M], A[M], b[M], c[M];
 
int main() {
	speed;
	cin >> n >> L;
	for(int i = 1, a, b; i < n; i++) {
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);		
	}
	for(int i = 1; i <= n; i++) {
		cin >> h[i];	
	}
	dfs(1, 0);
	p[1] = n + 1;
	for(int j = 1; j <= 40; j++) {
		p[n + j] = n + j + 1;		
	}
	for(int j = 1; j <= n; j++) {
		pr[j][0] = j;
		for(int i = 1; i <= 40; i++) {
			pr[j][i] = p[pr[j][i - 1]];
		}
	}
	cin >> q;
	for(int i = 1; i <= q; i++) {
		cin >> t[i] >> A[i];
		if(t[i] == 1)cin >> b[i] >> c[i];
		else ans[i] = 1;
	}
	for(int B = 40; B >= 0; B--) {
		for(int i = 1; i <= n + 40; i++) {
			dp[i] = 1;
		}
		for(int i = 1; i <= q; i++) {
			if(t[i] == 1 && b[i] != B)continue;
			int a = A[i];			
			if(t[i] == 1) {
				dp[a] = mul(dp[a], c[i]);
				b[i]--;
				A[i] = p[A[i]];
			} else {
				
				if(B != 0)
					ans[i] = mul(ans[i], dp[pr[a][B - 1]]);
				ans[i] = mul(ans[i], dp[pr[a][B]]);					
			}
		}
	}
	for(int i = 1; i <= q; i++) {
		if(t[i] == 2)cout << mul(h[A[i]], ans[i]) << "\n";
	}
}
/*
4 7
1 2
2 3
3 4
1 1 1 1
6
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 5 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 4 ms 5096 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 5 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 4 ms 5140 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 4 ms 5076 KB Output is correct
22 Correct 4 ms 5076 KB Output is correct
23 Correct 4 ms 5076 KB Output is correct
24 Correct 4 ms 5116 KB Output is correct
25 Correct 3 ms 5076 KB Output is correct
26 Correct 3 ms 5076 KB Output is correct
27 Correct 4 ms 5076 KB Output is correct
28 Correct 3 ms 5076 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 720 ms 64956 KB Output is correct
3 Correct 409 ms 61880 KB Output is correct
4 Correct 627 ms 67364 KB Output is correct
5 Correct 579 ms 63408 KB Output is correct
6 Correct 499 ms 63292 KB Output is correct
7 Correct 565 ms 63760 KB Output is correct
8 Correct 476 ms 64124 KB Output is correct
9 Correct 686 ms 70860 KB Output is correct
10 Correct 448 ms 67296 KB Output is correct
11 Correct 675 ms 64972 KB Output is correct
12 Correct 412 ms 61816 KB Output is correct
13 Correct 375 ms 62500 KB Output is correct
14 Correct 335 ms 62448 KB Output is correct
15 Correct 393 ms 62504 KB Output is correct
16 Correct 343 ms 62336 KB Output is correct
17 Correct 412 ms 62992 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5088 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 720 ms 64956 KB Output is correct
3 Correct 409 ms 61880 KB Output is correct
4 Correct 627 ms 67364 KB Output is correct
5 Correct 579 ms 63408 KB Output is correct
6 Correct 499 ms 63292 KB Output is correct
7 Correct 565 ms 63760 KB Output is correct
8 Correct 476 ms 64124 KB Output is correct
9 Correct 686 ms 70860 KB Output is correct
10 Correct 448 ms 67296 KB Output is correct
11 Correct 675 ms 64972 KB Output is correct
12 Correct 412 ms 61816 KB Output is correct
13 Correct 375 ms 62500 KB Output is correct
14 Correct 335 ms 62448 KB Output is correct
15 Correct 393 ms 62504 KB Output is correct
16 Correct 343 ms 62336 KB Output is correct
17 Correct 412 ms 62992 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5088 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 4 ms 5044 KB Output is correct
24 Correct 726 ms 64972 KB Output is correct
25 Correct 439 ms 61876 KB Output is correct
26 Correct 614 ms 69284 KB Output is correct
27 Correct 592 ms 63336 KB Output is correct
28 Correct 529 ms 63584 KB Output is correct
29 Correct 588 ms 63568 KB Output is correct
30 Correct 463 ms 64156 KB Output is correct
31 Correct 683 ms 69196 KB Output is correct
32 Correct 465 ms 67268 KB Output is correct
33 Correct 699 ms 64956 KB Output is correct
34 Correct 434 ms 61984 KB Output is correct
35 Correct 4 ms 5076 KB Output is correct
36 Correct 3 ms 5076 KB Output is correct
37 Correct 4 ms 5132 KB Output is correct
38 Correct 3 ms 5076 KB Output is correct
39 Correct 4 ms 5076 KB Output is correct
40 Correct 3 ms 5076 KB Output is correct
41 Correct 4 ms 5076 KB Output is correct
42 Correct 4 ms 5076 KB Output is correct
43 Correct 4 ms 5076 KB Output is correct
44 Correct 4 ms 5076 KB Output is correct
45 Correct 4 ms 5076 KB Output is correct
46 Correct 3 ms 5076 KB Output is correct
47 Correct 3 ms 5076 KB Output is correct
48 Correct 4 ms 5076 KB Output is correct
49 Correct 4 ms 5076 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 738 ms 68160 KB Output is correct
3 Correct 510 ms 65996 KB Output is correct
4 Correct 652 ms 66660 KB Output is correct
5 Correct 604 ms 61856 KB Output is correct
6 Correct 573 ms 62008 KB Output is correct
7 Correct 652 ms 62156 KB Output is correct
8 Correct 502 ms 62588 KB Output is correct
9 Correct 745 ms 66544 KB Output is correct
10 Correct 517 ms 66968 KB Output is correct
11 Correct 695 ms 62140 KB Output is correct
12 Correct 519 ms 63404 KB Output is correct
13 Correct 383 ms 69348 KB Output is correct
14 Correct 400 ms 69844 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 5 ms 5040 KB Output is correct
17 Correct 4 ms 5076 KB Output is correct
18 Correct 4 ms 5076 KB Output is correct
19 Correct 5 ms 5060 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 760 ms 68836 KB Output is correct
3 Correct 508 ms 65180 KB Output is correct
4 Correct 659 ms 67156 KB Output is correct
5 Correct 605 ms 63416 KB Output is correct
6 Correct 568 ms 63828 KB Output is correct
7 Correct 588 ms 63684 KB Output is correct
8 Correct 587 ms 64172 KB Output is correct
9 Correct 733 ms 70756 KB Output is correct
10 Correct 525 ms 67768 KB Output is correct
11 Correct 764 ms 65128 KB Output is correct
12 Correct 565 ms 64640 KB Output is correct
13 Correct 406 ms 69640 KB Output is correct
14 Correct 420 ms 69964 KB Output is correct
15 Correct 4 ms 5076 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 5 ms 5076 KB Output is correct
18 Correct 3 ms 5044 KB Output is correct
19 Correct 4 ms 5076 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 5 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 4 ms 5096 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 5 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 4 ms 5140 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 4 ms 5076 KB Output is correct
22 Correct 4 ms 5076 KB Output is correct
23 Correct 4 ms 5076 KB Output is correct
24 Correct 4 ms 5116 KB Output is correct
25 Correct 3 ms 5076 KB Output is correct
26 Correct 3 ms 5076 KB Output is correct
27 Correct 4 ms 5076 KB Output is correct
28 Correct 3 ms 5076 KB Output is correct
29 Correct 3 ms 5076 KB Output is correct
30 Correct 720 ms 64956 KB Output is correct
31 Correct 409 ms 61880 KB Output is correct
32 Correct 627 ms 67364 KB Output is correct
33 Correct 579 ms 63408 KB Output is correct
34 Correct 499 ms 63292 KB Output is correct
35 Correct 565 ms 63760 KB Output is correct
36 Correct 476 ms 64124 KB Output is correct
37 Correct 686 ms 70860 KB Output is correct
38 Correct 448 ms 67296 KB Output is correct
39 Correct 675 ms 64972 KB Output is correct
40 Correct 412 ms 61816 KB Output is correct
41 Correct 375 ms 62500 KB Output is correct
42 Correct 335 ms 62448 KB Output is correct
43 Correct 393 ms 62504 KB Output is correct
44 Correct 343 ms 62336 KB Output is correct
45 Correct 412 ms 62992 KB Output is correct
46 Correct 3 ms 5076 KB Output is correct
47 Correct 3 ms 5088 KB Output is correct
48 Correct 3 ms 5076 KB Output is correct
49 Correct 3 ms 5076 KB Output is correct
50 Correct 3 ms 5076 KB Output is correct
51 Correct 4 ms 5044 KB Output is correct
52 Correct 726 ms 64972 KB Output is correct
53 Correct 439 ms 61876 KB Output is correct
54 Correct 614 ms 69284 KB Output is correct
55 Correct 592 ms 63336 KB Output is correct
56 Correct 529 ms 63584 KB Output is correct
57 Correct 588 ms 63568 KB Output is correct
58 Correct 463 ms 64156 KB Output is correct
59 Correct 683 ms 69196 KB Output is correct
60 Correct 465 ms 67268 KB Output is correct
61 Correct 699 ms 64956 KB Output is correct
62 Correct 434 ms 61984 KB Output is correct
63 Correct 4 ms 5076 KB Output is correct
64 Correct 3 ms 5076 KB Output is correct
65 Correct 4 ms 5132 KB Output is correct
66 Correct 3 ms 5076 KB Output is correct
67 Correct 4 ms 5076 KB Output is correct
68 Correct 3 ms 5076 KB Output is correct
69 Correct 4 ms 5076 KB Output is correct
70 Correct 4 ms 5076 KB Output is correct
71 Correct 4 ms 5076 KB Output is correct
72 Correct 4 ms 5076 KB Output is correct
73 Correct 4 ms 5076 KB Output is correct
74 Correct 3 ms 5076 KB Output is correct
75 Correct 3 ms 5076 KB Output is correct
76 Correct 4 ms 5076 KB Output is correct
77 Correct 4 ms 5076 KB Output is correct
78 Correct 4 ms 5076 KB Output is correct
79 Correct 738 ms 68160 KB Output is correct
80 Correct 510 ms 65996 KB Output is correct
81 Correct 652 ms 66660 KB Output is correct
82 Correct 604 ms 61856 KB Output is correct
83 Correct 573 ms 62008 KB Output is correct
84 Correct 652 ms 62156 KB Output is correct
85 Correct 502 ms 62588 KB Output is correct
86 Correct 745 ms 66544 KB Output is correct
87 Correct 517 ms 66968 KB Output is correct
88 Correct 695 ms 62140 KB Output is correct
89 Correct 519 ms 63404 KB Output is correct
90 Correct 383 ms 69348 KB Output is correct
91 Correct 400 ms 69844 KB Output is correct
92 Correct 3 ms 5076 KB Output is correct
93 Correct 5 ms 5040 KB Output is correct
94 Correct 4 ms 5076 KB Output is correct
95 Correct 4 ms 5076 KB Output is correct
96 Correct 5 ms 5060 KB Output is correct
97 Correct 3 ms 5076 KB Output is correct
98 Correct 760 ms 68836 KB Output is correct
99 Correct 508 ms 65180 KB Output is correct
100 Correct 659 ms 67156 KB Output is correct
101 Correct 605 ms 63416 KB Output is correct
102 Correct 568 ms 63828 KB Output is correct
103 Correct 588 ms 63684 KB Output is correct
104 Correct 587 ms 64172 KB Output is correct
105 Correct 733 ms 70756 KB Output is correct
106 Correct 525 ms 67768 KB Output is correct
107 Correct 764 ms 65128 KB Output is correct
108 Correct 565 ms 64640 KB Output is correct
109 Correct 406 ms 69640 KB Output is correct
110 Correct 420 ms 69964 KB Output is correct
111 Correct 4 ms 5076 KB Output is correct
112 Correct 4 ms 5076 KB Output is correct
113 Correct 5 ms 5076 KB Output is correct
114 Correct 3 ms 5044 KB Output is correct
115 Correct 4 ms 5076 KB Output is correct
116 Correct 763 ms 71280 KB Output is correct
117 Correct 539 ms 73764 KB Output is correct
118 Correct 743 ms 79160 KB Output is correct
119 Correct 675 ms 73492 KB Output is correct
120 Correct 658 ms 73164 KB Output is correct
121 Correct 599 ms 73872 KB Output is correct
122 Correct 578 ms 74236 KB Output is correct
123 Correct 715 ms 78020 KB Output is correct
124 Correct 596 ms 77084 KB Output is correct
125 Correct 764 ms 72456 KB Output is correct
126 Correct 595 ms 73688 KB Output is correct
127 Correct 555 ms 74164 KB Output is correct
128 Correct 497 ms 74860 KB Output is correct
129 Correct 447 ms 75396 KB Output is correct