Submission #638656

#	Time	Username	Problem	Language	Result	Execution time	Memory
638656		valerikk	Sprinkler (JOI22_sprinkler)	C++17	12 / 100	709 ms	92188 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 50;
const int D = 41;

int n;
ll L;
vector<int> g[N];
ll h[N];
int par[N];
ll a[N][D];

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

void upd(int v, int d, int w) {
	for (int i = 0; i <= d; ++i, v = par[v]) {
		(a[v][d - i] *= w) %= L;
	}
}

int get(int v) {
	int res = 1;
	for (int i = 0; i < D; ++i, v = par[v]) {
		(res *= a[v][i]) %= L;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> L;
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
	}
	for (int i = n; i < n + D; ++i) {
		g[i].push_back(i + 1);
		g[i + 1].push_back(i);
	}
	g[0].push_back(n);
	g[n].push_back(0);
	dfs(n + D, n + D);
	for (int i = 0; i <= n + D; ++i) {
		for (int j = 0; j < D; ++j) {
			a[i][j] = 1;
		}
	}
	int q;
	cin >> q;
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			--x;
			upd(x, d, w); 
			upd(x, d - 1, w);
		}
		if (t == 2) {
			int x;
			cin >> x;
			--x;
			cout << h[x] * get(x) % L << "\n";
		}
	}
	return 0;
}

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