Submission #882882

#	Time	Username	Problem	Language	Result	Execution time	Memory
882882		NK_	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	627 ms	110420 KiB

sprinkler

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;

const int DEP = 45;
using AR = array<ll, 45>;


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, L; cin >> N >> L;

	V<vi> adj(N);
	for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}	

	vi H(N); for(auto& x : H) cin >> x;

	V<AR> W(N); vi par(N, -1); 
	function<void(int)> gen = [&](int u) {
		W[u].fill(1);
		for(auto& v : adj[u]) if (v != par[u]) {
			par[v] = u; gen(v);
		}
	};

	gen(0);

	int Q; cin >> Q;
	for(int q = 0; q < Q; q++) {
		int t; cin >> t;
		if (t == 1) {
			int u, d; ll x; cin >> u >> d >> x; --u;
			while(u != -1 && d >= 0) {
				W[u][d] = (W[u][d] * x) % L;
				// cout << u << " " << d << " --> " << W[u][d] << endl;
				u = par[u], d--;
			}
		} else {
			int u, d = 0; cin >> u; --u;

			ll mul = H[u];
			while(u != -1 && d < DEP) {
				if (par[u] == -1) { // all ones that have pivot points above bounds
					for(int dx = d; dx < DEP; dx++) {
						mul = (mul * W[u][dx]) % L;
					}
				} else {
					mul = (mul * W[u][d]) % L;
					if (d + 1 < DEP) mul = (mul * W[u][d + 1]) % L;
				}

				// cout << "Q: " << u << " " << d << " => " << mul << endl;
				u = par[u]; d++;
			}

			cout << mul << nl;
		}
	}

	exit(0-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