Submission #547416

#	Time	Username	Problem	Language	Result	Execution time	Memory
547416		skittles1412	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	2072 ms	81516 KiB

sprinkler

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 2e5 + 5;

int p[maxn];
vector<int> graph[maxn];

void dfs(int u, int par = -1) {
	p[u] = par;
	for (auto& v : graph[u]) {
		if (v != par) {
			dfs(v, u);
		}
	}
}

void solve() {
	int n;
	long mod;
	cin >> n >> mod;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	long arr[n];
	for (auto& a : arr) {
		cin >> a;
	}
	dfs(0);
	long mul[n][41];
	for (auto& a : mul) {
		fill(begin(a), end(a), 1);
	}
	int q;
	cin >> q;
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int u, d;
			long w;
			cin >> u >> d >> w;
			u--;
			for (int i = 0; i <= d; i++) {
				for (int j = 0; j + i <= d; j++) {
					if (i < d && p[u] != -1 && i + j + 2 <= d) {
						continue;
					}
					dbg(u, j, w);
					mul[u][j] = (mul[u][j] * w) % mod;
				}
				u = p[u];
				if (u == -1) {
					break;
				}
			}
		} else {
			int u;
			cin >> u;
			u--;
			long ans = arr[u];
			for (int i = 0; i <= 40; i++) {
				ans = (ans * mul[u][i]) % mod;
				u = p[u];
				if (u == -1) {
					break;
				}
			}
			cout << ans << endl;
		}
	}
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

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