Submission #689332

#	Time	Username	Problem	Language	Result	Execution time	Memory
689332		happypotato	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1320 ms	61176 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5;
const int mxD = 40;
int contrib[mxN + 1][mxD + 1];
vector<int> adj[mxN + 1];
int height[mxN + 1];
int n, L;
void Init() {
	for (int i = 1; i <= mxN; i++) {
		for (int j = 0; j <= mxD; j++) {
			contrib[i][j] = 1;
		}
	}
}
void Input() {
	cin >> n >> L;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		cin >> height[i];
	}
}
int par[mxN + 1];
void FindParent(int u = 1, int pp = 0) {
	par[u] = pp;
	for (int &v : adj[u]) {
		if (v != pp) {
			FindParent(v, u);
		}
	}
}
void Update(int x, int d, int w) {
	while (x != 1 && d >= 0) {
		contrib[x][d] = (1LL * contrib[x][d] * w) % L;
		if (d > 0) {
			contrib[x][d - 1] = (1LL * contrib[x][d - 1] * w) % L;
		}
		x = par[x];
		d--;
	}
	for (int i = d; i >= 0; i--) {
		contrib[x][i] = (1LL * contrib[x][i] * w) % L;
	}
}
int Query(int x) {
	int res = height[x];
	for (int i = 0; i <= mxD; i++) {
		if (x == 0) break;
		res = (1LL * res * contrib[x][i]) % L;
		x = par[x];
	}
	return res;
}
int main() {
	Init();
	Input();
	FindParent();
	int q;
	cin >> q;
	while (q--) {
		int cmd;
		cin >> cmd;
		if (cmd == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			Update(x, d, w);
		} else if (cmd == 2) {
			int x;
			cin >> x;
			cout << Query(x) << endl;
		}
	}
}

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