Submission #1049575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049575		ymm	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	402 ms	95588 KiB

sprinkler

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010, D = 42;
vector<int> A[N];
int par[N];
ll op[N][D];
ll ini[N];
int n, l;

void dfs(int v, int p)
{
	par[v] = p;
	for (int u : A[v]) {
		if (u != p)
			dfs(u, v);
	}
}

void do_op(int v, int d, int w)
{
	if (par[v] == -1) {
		Loop (i,0,d+1)
			op[v][i] = op[v][i] * w % l;
		return;
	}
	if (d == 0) {
		op[v][0] = op[v][0] * w % l;
		return;
	}
	op[v][d] = op[v][d] * w % l;
	op[v][d-1] = op[v][d-1] * w % l;
	do_op(par[v], d-1, w);
}

ll get(int v)
{
	int d = 0;
	ll x = ini[v] % l;
	while (v != -1 && d < D) {
		x = x * op[v][d] % l;
		v = par[v];
		d++;
	}
	return x;
}

int main()
{
	Loop (i,0,N) Loop (j,0,D)
		op[i][j] = 1;
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> l;
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A[v].push_back(u);
		A[u].push_back(v);
	}
	dfs(0, -1);
	Loop (i,0,n)
		cin >> ini[i];
	int q;
	cin >> q;
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			do_op(x-1, d, w);
		} else {
			int x;
			cin >> x;
			cout << get(x-1) << '\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