Submission #544600

#	Time	Username	Problem	Language	Result	Execution time	Memory
544600		sidon	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	837 ms	87052 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
#define int int64_t

const int Z = 2e5+1, B = 42;

int N, L, H[Z][B], W, res;

#define mul(VL) if((VL *= W) >= L) VL %= L

int p[Z];
vector<int> g[Z];

void dfs(int u) {
	for(const int &v : g[u]) if(v != p[u])
		p[v] = u, dfs(v);
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> L;

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

	dfs(1);

	for(int i = 0; i <= N; ++i)
		fill(H[i], H[i] + B, 1);

	for(int i = 1; i <= N; ++i)
		cin >> H[i][0];

	int Q, T, u, d; cin >> Q;
	for(int i = 1; i <= Q; ++i) {
		cin >> T >> u;
		if(T & 1) {
			cin >> d >> W;

			while(u) {
				mul(H[u][d]);
				if(d) {
					mul(H[u][d-1]);
					--d;
					u = p[u];
				} else break;
			}
			if(!u) {
				while(d) {
					mul(H[0][d]);
					--d;
				}
			}
		} else {
			res = H[u][0];
			u = p[u];

			for(d = 1; d < B; ++d) {
				(res *= H[u][d]) %= L;
				if(!u) break;
				u = p[u];
			}
			cout << res << '\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