Submission #625288

#	Time	Username	Problem	Language	Result	Execution time	Memory
625288		flappybird	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	824 ms	94656 KiB

sprinkler

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 202020
#define MAXS 41
#define INF 1000000000000000001
#define MOD 998244353
#define bb ' '
#define ln '\n'
#define Ln '\n'
ll L;
ll H[MAX];
ll mul[MAXS][MAX];
vector<int> adj[MAX];
int prt[MAX];
void dfs(int x, int p = 0) {
	prt[x] = p;
	for (auto v : adj[x]) if (v != p) dfs(v, x);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N >> L;
	int i, a, b;
	for (i = 1; i < N; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (i = 1; i <= N; i++) cin >> H[i];
	for (i = 1; i <= N; i++) for (int j = 0; j < MAXS; j++) mul[j][i] = 1;
	dfs(1);
	int Q;
	cin >> Q;
	while (Q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int X, D;
			ll W;
			cin >> X >> D >> W;
			if (D == 0) H[X] *= W, H[X] %= L;
			else {
				int v = X;
				while (1) {
					if (v == 1) {
						for (int k = 0; k <= D; k++) mul[k][v] *= W, mul[k][v] %= L;
						break;
					}
					else {
						if (!D) {
							H[v] *= W;
							H[v] %= L;
							break;
						}
						for (int k = D - 1; k <= D; k++) mul[k][v] *= W, mul[k][v] %= L;
						D--;
						v = prt[v];
					}
				}
			}
		}
		else {
			int v;
			cin >> v;
			int dis = 0;
			ll ans = H[v];
			int x = v;
			while (1) {
				if (dis > 40) break;
				if (!x) break;
				ans *= mul[dis][x];
				ans %= L;
				dis++;
				x = prt[x];
			}
			cout << ans << ln;
		}
	}
}

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