Submission #1130876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130876		nguyenkhangninh99	Sprinkler (JOI22_sprinkler)	C++20	9 / 100	1365 ms	185264 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn = 2e5 + 69;

vector<int> g[maxn];

int mod;

int h[maxn];
int depth[maxn], par[maxn];
int f[maxn][100];

void dfs(int u, int pre){
	depth[u] = depth[pre] + 1;
	par[u] = pre;
	for(int v: g[u]){
		if(v == pre) continue;
		dfs(v, u);
	}
}
void solve(){
	int n; cin >> n >> mod;

	for(int i = 1; i <= n - 1; i++){
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	for(int i = 1; i <= n; i++) cin >> h[i];

	dfs(1, 0);
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 100; j++) f[i][j] = 1;
	}

	int q; cin >> q;

	while(q--){
		int type; cin >> type;
		if(type == 1){
			int u, d, w; cin >> u >> d >> w;
			if(d == 0) (f[u][d] *= w) %= mod;
			else{
				int temp = d;
				for(int i = 0; i + 2 <= temp; i++){
					(f[u][d] *= w) %= mod;
					(f[u][d - 1] *= w) %= mod;
					///cout << u << " " << d << "\n";
					d -= 1;
					u = par[u];
					if(!u) break;
				}

				if(!u){
					for(int j = 0; j <= d; j++) (f[1][j] *= w) %= mod;
				}
				if(u){
					(f[u][0] *= w) %= mod;
					(f[u][1] *= w) %= mod;
					(f[par[u]][0] *= w) %= mod;
				}
			}
		}

		else{
			int u; cin >> u;
			int res = h[u];
        	for (int d = 0; u && d < 40; d++, u = par[u]){
				res = (res * f[u][d]) % mod;
				//cout << u << " " <<d << " " << f[u][d] << "\n";
			}
        	cout << res << "\n";
		}
		
	}
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	solve();
}

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