Submission #1274410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274410		coderpemula	Sprinkler (JOI22_sprinkler)	C++20	38 / 100	4104 ms	175620 KiB

sprinkler

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;
vector<int>v[200001];
int mod,n,dp[200001][41][2],anu[200001],idx[200001],par[200001],tree[800001],lazy[800001];
void propagate(int node, int st, int en){
	if(st == en){
		//if(st == 1 and en == 1) cout<<"cek : "<<node<<" "<<tree[node]<<endl;
		tree[node] = tree[node]*lazy[node]%mod;
		lazy[node] = 1;
		return;
	}
	lazy[node*2] = lazy[node*2]*lazy[node]%mod;
	lazy[node*2+1] = lazy[node*2+1]*lazy[node]%mod;
	lazy[node] = 1;
}
int query(int node, int st, int en, int idx){
	propagate(node,st,en);
	if(st > idx or en < idx) return 1;
	if(st == en) return tree[node];
	int mid = (st+en)/2;
	int q1 = query(node*2,st,mid,idx);
	int q3 = query(node*2+1,mid+1,en,idx);
	return q1*q3%mod;
}
void upd(int node, int st, int en, int L, int R, int val){
	propagate(node,st,en);
	if(st > R or en < L) return;
	if(st >= L and en <= R){
		lazy[node] = lazy[node]*val%mod;
		propagate(node,st,en);
	}
	else{
		int mid = (st+en)/2;
		upd(node*2,st,mid,L,R,val);
		upd(node*2+1,mid+1,en,L,R,val);
		tree[node] = tree[node*2]*tree[node*2+1]%mod;
	}
}
// 0 = left, 1 = right
void dfs(int node){
	dp[node][0][0] = dp[node][0][1] = idx[node];
	int i;
	for(i=1;i<=40;i++) dp[node][i][0] = 1e9, dp[node][i][1] = -1e9;
	for(auto x:v[node]){
		if(x == par[node]) continue;
		par[x] = node;
		dfs(x);
		for(i=0;i<=39;i++){
			if(dp[x][i][0] == 1e9) break;
			dp[node][i+1][0] = min(dp[node][i+1][0],dp[x][i][0]);
			dp[node][i+1][1] = max(dp[node][i+1][1],dp[x][i][1]);
		}
	}
}
int pangkat(int base ,int con){
	if(con == 0) return 1;
	int temp = pangkat(base,con/2);
	if(con&1) return temp*temp%mod*base%mod;
	return temp*temp%mod;
}
signed main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int i,j,t,tin=2,x,d,qt;
	cin>>n>>mod;
	for(i=1;i<n;i++){
		cin>>j>>t;
		v[j].pb(t);
		v[t].pb(j);
	}
	for(i=1;i<=n;i++) cin>>anu[i];
	for(i=1;i<=4*n;i++) tree[i] = 1;
	for(i=1;i<=4*n;i++) lazy[i] = 1;
	///cout<<tree[4]<<" TREE 4"<<endl;
	queue<int>q;
	q.push(1);
	idx[1] = 1;
	while(!q.empty()){
		int node = q.front();
		q.pop();
		//cout<<node<<endl;
		for(auto x:v[node]){
			if(idx[x] == 0){
				idx[x] = tin;
				tin++;
				q.push(x);
			}
		}
	}
//	for(i=1;i<=n;i++) cout<<idx[i]<<" ";
//	cout<<endl;
	par[1] = 0;
	dfs(1);
	//cout<<dp[1][1][0]<<" "<<dp[1][1][1]<<endl;
	cin>>qt;
	vector<int>tmp;
	while(qt--){
		cin>>t;
		if(t == 1){
			cin>>x>>d>>j;
			int dist = d,node=x, str = 0;
			while(true){
				if(par[node] == 0 or dist == 0) break;
				tmp.pb(node);
				dist--;
				node = par[node];
			}
			tmp.pb(node);
			while(!tmp.empty()){
				node = tmp.back();
				tmp.pop_back();
				//cout<<node<<" "<<str<<" "<<dist<<endl;
				if(dp[node][str][0] == 1e9) break;
				for(i=str;i<=dist;i++){
					if(dp[node][i][0] == 1e9) break;
					//cout<<dp[node][i][0]<<" cek "<<dp[node][i][1]<<" "<<j<<endl;
					upd(1,1,n,dp[node][i][0],dp[node][i][1],j);
				}
				str = dist;
				dist++;
			}
		}
		else cin>>j, cout<<anu[j]*query(1,1,n,idx[j])%mod<<"\n";
	}
	
	return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17