제출 #864500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
864500		willychan	Sprinkler (JOI22_sprinkler)	C++14	9 / 100	489 ms	53588 KiB

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
• Subtask 2: 9 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17