Submission #917480

#	Time	Username	Problem	Language	Result	Execution time	Memory
917480		PotatoMan	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	963 ms	100400 KiB

sprinkler

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