Submission #864500

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
864500	2023-10-23T05:48:06 Z	willychan	Sprinkler (JOI22_sprinkler)	C++14	9 / 100	489 ms	53588 KB

sprinkler

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds

const int N = 2e5+5;
int ans[N];
const int D = 42;
int app[N][D];
vector<int> side[N];
int L = 0;
int p[N];
int n;
void dfs(int cur){
	for(auto i : side[cur]){
		if(!p[i]){
			p[i]=cur;
			dfs(i);
		}
	}
}
void debug(){
	cout<<"\n\n\n";
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	cout<<"\n";
	for(int i=1;i<=n;i++){
		for(int j=0;j<(min(D,n+1));j++){
			cout<<app[i][j]<<" ";
		}
		cout<<"\n";
	}
	cout<<"\n\n\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>L;
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		side[a].push_back(b);
		side[b].push_back(a);
	}
	for(int i=1;i<=n;i++){
		for(int d=0;d<D;d++) app[i][d]=1;
		int a;cin>>a;
		ans[i]=a;
	}
	p[1]=1;
	dfs(1);
	//for(int i=1;i<=n;i++) cout<<p[i]<<" ";
	//cout<<"p\n";
	int Q;cin>>Q;
	while(Q--){
		int t; cin>>t;
		if(t==1){
			int x,d,w;cin>>x>>d>>w;	
			for(int i=0;i<=d;i++){
				ans[x] = (1LL*ans[x]*w)%L;
				if(i!=d) app[x][d] = (1LL*app[x][d]*w)%L;
				if(x==1) break;
				x = p[x];
			}
			//debug();
		}else{
			int x;cin>>x;
			bool works = 0;
			int rans = ans[x];
			for(int i=0;i<=40;i++){
				if(x==1) works=1;
				//cout<<x<<"t"<<i<<"\n";
				rans = (1LL*rans*app[x][i])%L;
				if(works==1) break;
				x = p[x];
			}
			cout<<rans<<"\n";
		}
	}
	return 0;
}

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6488 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Incorrect	1 ms	6492 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6488 KB	Output is correct
2	Correct	338 ms	49696 KB	Output is correct
3	Correct	221 ms	46196 KB	Output is correct
4	Correct	319 ms	50488 KB	Output is correct
5	Correct	316 ms	48100 KB	Output is correct
6	Correct	204 ms	47828 KB	Output is correct
7	Correct	201 ms	47952 KB	Output is correct
8	Correct	168 ms	48552 KB	Output is correct
9	Correct	459 ms	53588 KB	Output is correct
10	Correct	238 ms	50004 KB	Output is correct
11	Correct	329 ms	49268 KB	Output is correct
12	Correct	242 ms	46260 KB	Output is correct
13	Correct	155 ms	46788 KB	Output is correct
14	Correct	162 ms	46792 KB	Output is correct
15	Correct	167 ms	46872 KB	Output is correct
16	Correct	164 ms	46676 KB	Output is correct
17	Correct	166 ms	47444 KB	Output is correct
18	Correct	1 ms	6488 KB	Output is correct
19	Correct	2 ms	6492 KB	Output is correct
20	Correct	1 ms	6492 KB	Output is correct
21	Correct	1 ms	6492 KB	Output is correct
22	Correct	1 ms	6492 KB	Output is correct

Subtask #3
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6488 KB	Output is correct
2	Correct	338 ms	49696 KB	Output is correct
3	Correct	221 ms	46196 KB	Output is correct
4	Correct	319 ms	50488 KB	Output is correct
5	Correct	316 ms	48100 KB	Output is correct
6	Correct	204 ms	47828 KB	Output is correct
7	Correct	201 ms	47952 KB	Output is correct
8	Correct	168 ms	48552 KB	Output is correct
9	Correct	459 ms	53588 KB	Output is correct
10	Correct	238 ms	50004 KB	Output is correct
11	Correct	329 ms	49268 KB	Output is correct
12	Correct	242 ms	46260 KB	Output is correct
13	Correct	155 ms	46788 KB	Output is correct
14	Correct	162 ms	46792 KB	Output is correct
15	Correct	167 ms	46872 KB	Output is correct
16	Correct	164 ms	46676 KB	Output is correct
17	Correct	166 ms	47444 KB	Output is correct
18	Correct	1 ms	6488 KB	Output is correct
19	Correct	2 ms	6492 KB	Output is correct
20	Correct	1 ms	6492 KB	Output is correct
21	Correct	1 ms	6492 KB	Output is correct
22	Correct	1 ms	6492 KB	Output is correct
23	Incorrect	1 ms	6492 KB	Output isn't correct
24	Halted	0 ms	0 KB	-