Submission #893341

#	Time	Username	Problem	Language	Result	Execution time	Memory
893341		iskhakkutbilim	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	881 ms	118100 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) a.begin(), a.end()

int mod;
void prod(int &a, int b){
	a = (a * b) % mod;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n; cin >> n >> mod;
	vector< vector<int> > g(n+1);
	for(int i = 1;i < n; i++){
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	vector< vector<int> > ans(n+1, vector<int>(42, 1));
	vector<int> up(n+1), h(n+1);
	for(int i = 1;i <= n; i++){
		cin >> h[i];
	}
	function<void(int, int)> dfs=[&](int v, int par){
		up[v] = par;
		for(int to : g[v]){
			if(to == par) continue;
			dfs(to, v);
		}
	};
	dfs(1, -1);
	int q; cin >> q;
	while(q--){
		int t; cin >> t;
		if(t == 1){
			int v, d, w; cin >> v >> d >> w;
			int cur = v;
			while(up[cur] != -1 && d > 0){
				prod(ans[cur][d], w);
				prod(ans[cur][d-1], w);
				cur = up[cur];
				d--;
			}
			while(d >= 0){
				prod(ans[cur][d], w);
				d--;
			}
		}else{
			int v; cin >> v;
			
			int product = h[v];
			for(int i = 0;i <= 40 && v != -1; i++, v = up[v]){
				prod(product, ans[v][i]);
			}
			cout << product << '\n';
			
		}
	}
	
	return 0;
}

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