Submission #572239

#	Time	Username	Problem	Language	Result	Execution time	Memory
572239		8e7	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	872 ms	100156 KiB

sprinkler

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define maxd 42
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int mod;
ll mul[maxn][maxd];
vector<int> adj[maxn];
int par[maxn];
void dfs(int n, int pa) {
	par[n] = pa;
	for (int v:adj[n]) {
		if (v != pa) {
			dfs(v, n);
		}
	}
	for (int i = 0;i < maxd;i++) mul[n][i] = 1;
	//debug(n, leaf[n]);
}
ll h[maxn];
void modify(int n, int d, int w) {
	while (d >= 0 && n) {
		mul[n][d] = mul[n][d] * w % mod;
		if (d > 0) mul[n][d-1] = mul[n][d-1] * w % mod;
		if (n == 1) {
			for (int x = d - 2;x >= 0;x--) mul[n][x] = mul[n][x] * w % mod;
			break;
		}
		n = par[n];
		d--;
	}
}
ll query(int n) {
	ll ret = h[n];
	int cur = 0;
	while (cur < maxd && n) {
		ret = ret * mul[n][cur] % mod;
		n = par[n];
		cur++;
	}
	return ret;
}
int main() {
	io
	int n;
	cin >> n >> mod;
	for (int i = 0;i < n - 1;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1;i <= n;i++) cin >> h[i]; 
	dfs(1, 0);
	int q;
	cin >> q;
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			modify(x, d, w);
		} else {
			int x;
			cin >> x;
			cout << query(x) << "\n";
		}
	}
}

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