Submission #793084

#	Time	Username	Problem	Language	Result	Execution time	Memory
793084		MetalPower	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	773 ms	64544 KiB

sprinkler

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

const int MX = 2e5 + 10;
const int MK = 45;

vector<int> adj[MX];
int N, L, Q, p[MX], h[MX], dp[MX][MK];

// dp[i][j] is the multiplication towards all of node i's descendants that are of distance d
// Update is updating all dp[anc_i][D - dist(anc_i, i)] 
// But observe that this won't handle cases where we go back up and return through the path we came from
// that is why we also add dp[anc_i][D - dist(anc_i, i) - 1]
// Query is querying all dp[anc_i][dist(anc_i, i)]

void dfs(int u, int v){
	p[u] = v;
	for(int nxt : adj[u]){
		if(nxt == v) continue;
		dfs(nxt, u);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> L;
	for(int i = 1; i < N; 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 >> h[i];

	dfs(1, 0);

	for(int i = 0; i < MX; i++)
		for(int j = 0; j < MK; j++) dp[i][j] = 1;

	cin >> Q;
	for(int i = 1; i <= Q; i++){
		int t, x, d, w; cin >> t;

		if(t == 1){
			cin >> x >> d >> w;
			dp[x][d] = 1ll * dp[x][d] * w % L;
			if(x != 1 && d > 0) dp[x][d - 1] = 1ll * dp[x][d - 1] * w % L;
			int curr = x;
			for(int j = 1; j <= d; j++){
				if(p[curr] != 0) curr = p[curr];
				dp[curr][d - j] = 1ll * dp[curr][d - j] * w % L;
				if(curr != 1 && d > j) dp[curr][d - j - 1] = 1ll * dp[curr][d - j - 1] * w % L;
			}
		}else{
			cin >> x;
			int ans = h[x], curr = x;
			for(int j = 0; j <= 41; j++){
				// cout << "At query #" << i << " := anc " << x << " " << curr << " " << j << " " << dp[curr][j] << '\n';
				ans = 1ll * ans * dp[curr][j] % L;
				if(p[curr] == 0) break;
				else curr = p[curr];
			}
			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