Submission #587282

#	Time	Username	Problem	Language	Result	Execution time	Memory
587282		dutinmeow	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1588 ms	70888 KiB

sprinkler

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

#pragma region y_combinator

#ifndef Y_COMBINATOR_HPP
#define Y_COMBINATOR_HPP

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

#endif

#pragma endregion y_combinator

const int $D = 50;

int MOD;

struct mint {
	int v;

	mint() : v(0) {}

	mint(int _v) : v(_v % MOD) {}

	mint &operator+=(const mint &rhs) { 
		v += rhs.v;
		if (v >= MOD)
			v -= MOD;
		return *this;
	}

	mint &operator-=(const mint &rhs) { 
		v -= rhs.v;
		if (v < 0)
			v += MOD;
		return *this;
	}

	mint &operator*=(const mint &rhs) { 
		v = static_cast<long long>(v) * rhs.v % MOD;
		return *this;
	}
};

mint operator+(mint lhs, const mint &rhs) { return lhs += rhs; }

mint operator-(mint lhs, const mint &rhs) { return lhs -= rhs; }

mint operator*(mint lhs, const mint &rhs) { return lhs *= rhs; }

istream &operator>>(istream &is, mint &m) { return is >> m.v; }

ostream &operator<<(ostream &os, const mint &m) { return os << m.v; }

int main() {
	int N;
	cin >> N >> MOD;
	vector<vector<int>> T(N);
	for (int i = 1; i < N; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		T[u].push_back(v);
		T[v].push_back(u);
	}

	vector<int> par(N);
	par[0] = -1;

	y_combinator([&](auto dfs, int u) -> void {
		for (int v : T[u]) {
			if (v == par[u])
				continue;
			par[v] = u;
			dfs(v);
		}
	})(0);

	vector<mint> A(N);
	for (mint &a : A)
		cin >> a;
	
	vector<array<mint, $D>> L(N);
	for_each(L.begin(), L.end(), [](auto &t) { t.fill(mint(1)); });
	
	int Q;
	cin >> Q;
	while (Q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int s, d;
			mint v;
			cin >> s >> d >> v;
			s--;

			y_combinator([&](auto dfs, int u, int c) -> void {
				if (u == -1 || c > d)
					return;
				dfs(par[u], c + 1);
				if (u == 0) {	
					for (int i = 0; i <= d - c; i++)
						L[u][i] *= v;
				} else {
					if (d - c - 1 >= 0)
						L[u][d - c - 1] *= v;
					L[u][d - c] *= v;
				}
			})(s, 0);
		} else {
			int u;
			cin >> u;
			u--;
			mint ans = A[u];
			for (int d = 0; u != -1 && d < $D; d++) {
				ans *= L[u][d];
				u = par[u];
			}
			cout << ans << '\n';
		}
	}
}

Compilation message (stderr)

sprinkler.cpp:4: warning: ignoring '#pragma region y_combinator' [-Wunknown-pragmas]
    4 | #pragma region y_combinator
      | 
sprinkler.cpp:29: warning: ignoring '#pragma endregion y_combinator' [-Wunknown-pragmas]
   29 | #pragma endregion y_combinator
      |

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