oj.uz

Submission #917480

# Submission time Handle Problem Language Result Execution time Memory
917480 2024-01-28T09:49:51 Z PotatoMan Sprinkler (JOI22_sprinkler) C++14
100 / 100
 963 ms 100400 KB 
#include <bits/stdc++.h>
#define inf INT_MAX
#define longlonginf LONG_LONG_MAX
#define mod 998244353
#define MAXN 200005
#define pii pair<ll,ll>
#define ll long long
#define deb(x) cerr<<"[ "<<#x<<" = "<<x<<" ]";
#define yes() cout<<"YES\n";
#define no() cout<<"NO\n";
using namespace std;
 
ll n,k,m,q,cur,z;
ll ans = 0;
string subtask;
string s;
ll bit[MAXN][45];

void update(ll x,ll y,ll d){
	for(int i = y ; i <= 41 ; i += i&(-i)){
		bit[x][i] *= d;
		bit[x][i] %= m;
	}
}

ll get_res(ll x,ll y){
	ll res = 1;
	for(int i = y ; i > 0 ; i -= i&(-i)){
		res *= bit[x][i];
		res %= m;
	}
	return res;
}

void solve(){
	cin>>n>>m;
	vector<vector<ll>> adj(n+5);
	for(int i = 0 ; i < n-1 ; i++){
		ll l,r;
		cin>>l>>r;
		adj[l].push_back(r);
		adj[r].push_back(l);
	}
	ll h[n+5];
	for(int i = 1 ; i <= n ; i++) cin>>h[i];
	ll par[n+5];
	par[1] = 0;
	queue<int> p;
	p.push(1);
	bool vis[n+5];
	memset(vis,0,sizeof(vis));
	vis[1] = 1;
	while(!p.empty()){
		ll x = p.front();
		p.pop();
		for(auto u : adj[x]){
			if(vis[u]) continue;
			par[u] = x;
			vis[u] = 1;
			p.push(u);
		}
	}
	//init
	for(int i = 1 ; i <= n ; i++){
		for(int j = 0 ; j <= 41 ; j++){
			bit[i][j] = 1;
		}
	}
	//queries
	cin>>q;
	while(q--){
		ll x;
		cin>>x;
		if( x == 1 ){
			ll tx,td,tw;
			cin>>tx>>td>>tw;
			cur = tx;
			while(td+1 && cur){
				if( cur == 1 ) update(cur,40-td+1,tw);
				else {
					bit[cur][40-td+1] *= tw;
					bit[cur][40-td+1] %= m;
					if( td != 0 ) {
						bit[cur][40-td+2] *= tw;
						bit[cur][40-td+2] %= m;
					}
				}
				td--;
				cur = par[cur];
			}
		}
		else{
			ll tx,td;
			cin>>tx;
			td = 0;
			cur = tx;
			ll res = h[tx];
			while(cur && td <= 40){
				if( cur == 1 ) res *= get_res(cur,40-td+1);
				else res *= bit[cur][40-td+1];
				res %= m;
				td++;
				cur = par[cur];
			}
			cout<<res<<"\n";
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//cin>>T;
	for(int i = 0 ; i < T ; i++){
		//cout<<"Case #"<<i+1<<": ";
		solve();
	}
	return 0;
}
 
/*
	out of bound for loop
	(constraint change in loop)
	forget to change bool to int
	misread -> missed subtask
	you thought u declared it huh?
	not i but x
	logical operator
	wrong example/proof
	thoroughly
	wrong variables
	thinking it wrong
	bruh just try some test case
	capitals ;-;
	wrong data structure lol
	count memory usement
	corner case
	oversized array
	orders
	statements
	size initializer
	while con
	map -> array
	wrong digits??
	swapped variables??
	check if theres any variabled
	that got declared twice
	find some pattern
	name collision
	constraints??!
	mod !!
	resets
*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2784 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 476 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 472 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 468 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 444 ms 89796 KB Output is correct
3 Correct 295 ms 98640 KB Output is correct
4 Correct 488 ms 96920 KB Output is correct
5 Correct 392 ms 98148 KB Output is correct
6 Correct 281 ms 98128 KB Output is correct
7 Correct 280 ms 98724 KB Output is correct
8 Correct 231 ms 99644 KB Output is correct
9 Correct 670 ms 96608 KB Output is correct
10 Correct 323 ms 97336 KB Output is correct
11 Correct 477 ms 97844 KB Output is correct
12 Correct 300 ms 98348 KB Output is correct
13 Correct 191 ms 99268 KB Output is correct
14 Correct 247 ms 99340 KB Output is correct
15 Correct 185 ms 98740 KB Output is correct
16 Correct 208 ms 98896 KB Output is correct
17 Correct 224 ms 99412 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 444 ms 89796 KB Output is correct
3 Correct 295 ms 98640 KB Output is correct
4 Correct 488 ms 96920 KB Output is correct
5 Correct 392 ms 98148 KB Output is correct
6 Correct 281 ms 98128 KB Output is correct
7 Correct 280 ms 98724 KB Output is correct
8 Correct 231 ms 99644 KB Output is correct
9 Correct 670 ms 96608 KB Output is correct
10 Correct 323 ms 97336 KB Output is correct
11 Correct 477 ms 97844 KB Output is correct
12 Correct 300 ms 98348 KB Output is correct
13 Correct 191 ms 99268 KB Output is correct
14 Correct 247 ms 99340 KB Output is correct
15 Correct 185 ms 98740 KB Output is correct
16 Correct 208 ms 98896 KB Output is correct
17 Correct 224 ms 99412 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 507 ms 97864 KB Output is correct
25 Correct 334 ms 98548 KB Output is correct
26 Correct 504 ms 97104 KB Output is correct
27 Correct 428 ms 98168 KB Output is correct
28 Correct 303 ms 98436 KB Output is correct
29 Correct 274 ms 98144 KB Output is correct
30 Correct 254 ms 99508 KB Output is correct
31 Correct 717 ms 96820 KB Output is correct
32 Correct 359 ms 97308 KB Output is correct
33 Correct 454 ms 97776 KB Output is correct
34 Correct 346 ms 98364 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 1 ms 348 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 1 ms 468 KB Output is correct
49 Correct 0 ms 348 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 734 ms 86052 KB Output is correct
3 Correct 909 ms 85420 KB Output is correct
4 Correct 657 ms 85608 KB Output is correct
5 Correct 434 ms 86608 KB Output is correct
6 Correct 300 ms 86804 KB Output is correct
7 Correct 279 ms 87120 KB Output is correct
8 Correct 229 ms 87900 KB Output is correct
9 Correct 782 ms 86080 KB Output is correct
10 Correct 894 ms 85456 KB Output is correct
11 Correct 536 ms 86940 KB Output is correct
12 Correct 473 ms 86368 KB Output is correct
13 Correct 350 ms 87120 KB Output is correct
14 Correct 355 ms 87888 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 504 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 757 ms 88756 KB Output is correct
3 Correct 903 ms 85560 KB Output is correct
4 Correct 665 ms 87380 KB Output is correct
5 Correct 530 ms 88148 KB Output is correct
6 Correct 332 ms 97036 KB Output is correct
7 Correct 343 ms 96848 KB Output is correct
8 Correct 252 ms 97732 KB Output is correct
9 Correct 791 ms 96576 KB Output is correct
10 Correct 937 ms 95016 KB Output is correct
11 Correct 583 ms 97476 KB Output is correct
12 Correct 575 ms 95932 KB Output is correct
13 Correct 369 ms 96844 KB Output is correct
14 Correct 396 ms 97616 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2784 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 476 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 472 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 444 ms 89796 KB Output is correct
31 Correct 295 ms 98640 KB Output is correct
32 Correct 488 ms 96920 KB Output is correct
33 Correct 392 ms 98148 KB Output is correct
34 Correct 281 ms 98128 KB Output is correct
35 Correct 280 ms 98724 KB Output is correct
36 Correct 231 ms 99644 KB Output is correct
37 Correct 670 ms 96608 KB Output is correct
38 Correct 323 ms 97336 KB Output is correct
39 Correct 477 ms 97844 KB Output is correct
40 Correct 300 ms 98348 KB Output is correct
41 Correct 191 ms 99268 KB Output is correct
42 Correct 247 ms 99340 KB Output is correct
43 Correct 185 ms 98740 KB Output is correct
44 Correct 208 ms 98896 KB Output is correct
45 Correct 224 ms 99412 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 1 ms 348 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 1 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 507 ms 97864 KB Output is correct
53 Correct 334 ms 98548 KB Output is correct
54 Correct 504 ms 97104 KB Output is correct
55 Correct 428 ms 98168 KB Output is correct
56 Correct 303 ms 98436 KB Output is correct
57 Correct 274 ms 98144 KB Output is correct
58 Correct 254 ms 99508 KB Output is correct
59 Correct 717 ms 96820 KB Output is correct
60 Correct 359 ms 97308 KB Output is correct
61 Correct 454 ms 97776 KB Output is correct
62 Correct 346 ms 98364 KB Output is correct
63 Correct 0 ms 344 KB Output is correct
64 Correct 1 ms 348 KB Output is correct
65 Correct 1 ms 348 KB Output is correct
66 Correct 1 ms 348 KB Output is correct
67 Correct 1 ms 348 KB Output is correct
68 Correct 1 ms 348 KB Output is correct
69 Correct 1 ms 344 KB Output is correct
70 Correct 1 ms 344 KB Output is correct
71 Correct 1 ms 348 KB Output is correct
72 Correct 1 ms 348 KB Output is correct
73 Correct 1 ms 348 KB Output is correct
74 Correct 1 ms 348 KB Output is correct
75 Correct 1 ms 348 KB Output is correct
76 Correct 1 ms 468 KB Output is correct
77 Correct 0 ms 348 KB Output is correct
78 Correct 0 ms 348 KB Output is correct
79 Correct 734 ms 86052 KB Output is correct
80 Correct 909 ms 85420 KB Output is correct
81 Correct 657 ms 85608 KB Output is correct
82 Correct 434 ms 86608 KB Output is correct
83 Correct 300 ms 86804 KB Output is correct
84 Correct 279 ms 87120 KB Output is correct
85 Correct 229 ms 87900 KB Output is correct
86 Correct 782 ms 86080 KB Output is correct
87 Correct 894 ms 85456 KB Output is correct
88 Correct 536 ms 86940 KB Output is correct
89 Correct 473 ms 86368 KB Output is correct
90 Correct 350 ms 87120 KB Output is correct
91 Correct 355 ms 87888 KB Output is correct
92 Correct 0 ms 344 KB Output is correct
93 Correct 0 ms 348 KB Output is correct
94 Correct 0 ms 348 KB Output is correct
95 Correct 0 ms 348 KB Output is correct
96 Correct 1 ms 504 KB Output is correct
97 Correct 1 ms 348 KB Output is correct
98 Correct 757 ms 88756 KB Output is correct
99 Correct 903 ms 85560 KB Output is correct
100 Correct 665 ms 87380 KB Output is correct
101 Correct 530 ms 88148 KB Output is correct
102 Correct 332 ms 97036 KB Output is correct
103 Correct 343 ms 96848 KB Output is correct
104 Correct 252 ms 97732 KB Output is correct
105 Correct 791 ms 96576 KB Output is correct
106 Correct 937 ms 95016 KB Output is correct
107 Correct 583 ms 97476 KB Output is correct
108 Correct 575 ms 95932 KB Output is correct
109 Correct 369 ms 96844 KB Output is correct
110 Correct 396 ms 97616 KB Output is correct
111 Correct 1 ms 348 KB Output is correct
112 Correct 0 ms 348 KB Output is correct
113 Correct 1 ms 348 KB Output is correct
114 Correct 1 ms 348 KB Output is correct
115 Correct 0 ms 348 KB Output is correct
116 Correct 549 ms 95944 KB Output is correct
117 Correct 566 ms 98656 KB Output is correct
118 Correct 682 ms 97340 KB Output is correct
119 Correct 460 ms 98140 KB Output is correct
120 Correct 371 ms 98064 KB Output is correct
121 Correct 336 ms 98976 KB Output is correct
122 Correct 258 ms 99672 KB Output is correct
123 Correct 843 ms 96852 KB Output is correct
124 Correct 963 ms 97008 KB Output is correct
125 Correct 562 ms 97092 KB Output is correct
126 Correct 615 ms 98520 KB Output is correct
127 Correct 659 ms 98972 KB Output is correct
128 Correct 482 ms 99664 KB Output is correct
129 Correct 507 ms 100400 KB Output is correct