Submission #544546

#	Time	Username	Problem	Language	Result	Execution time	Memory
544546		benson1029	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	1259 ms	85632 KiB

sprinkler

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

int n, l, s, t;
vector<int> edg[200045];
long long h[200045];
int q;
int op, x, d, k;
int anc[200045];
long long v[200045][41];

void dfs(int x, int p) {
	anc[x] = p;
	for(int i:edg[x]) {
		if(i!=p) {
			dfs(i, x);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> l;
	for(int i=0; i<n-1; i++) {
		cin >> s >> t;
		edg[s].push_back(t);
		edg[t].push_back(s);
	}
	for(int i=1; i<=n; i++) {
		cin >> h[i];
	}
	for(int i=n+1; i<n+40; i++) {
		edg[i].push_back(i+1);
	}
	edg[n+40].push_back(1);
	dfs(n+1, -1);
	cin >> q; 
	for(int i=1; i<=n+40; i++) {
		for(int j=0; j<=40; j++) {
			v[i][j] = 1;
		}
	}
	while(q--) {
		cin >> op >> x;
		if(op==1) {
			cin >> d >> k;
			int ptr = x;
			for(int i=0; i<=d; i++) {
				v[ptr][d-i] = (v[ptr][d-i] * k) % l;
				if(i<d) v[ptr][d-1-i] = (v[ptr][d-1-i] * k) % l;
				ptr = anc[ptr];
			}
		} else {
			int ptr = x;
			long long ans = h[x];
			for(int i=0; i<=40; i++) {
				ans = (ans * v[ptr][i]) % l;
				ptr = anc[ptr];
			}
			cout << ans << "\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