Submission #551937

#	Time	Username	Problem	Language	Result	Execution time	Memory
551937		QwertyPi	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	1363 ms	99444 KiB

sprinkler

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define int long long
using namespace std;

const int N = 2e5 + 5, D = 41;
int n, L;
int h[N], p[N], d[N];
vector<int> G[N];
int dp[N][D];

void dfs(int x, int par = -1){
	for(auto i : G[x]){
		if(i != par){
			d[i] = d[x] + 1;
			dfs(i, x);
			p[i] = x;
		}
	}
}

int lay[D];
void upd(int x, int d, int w){
	int idx = 0;
	while(x != 0 && idx <= d){
		lay[idx++] = x;
		x = p[x];
	}
	int mx = 0;
	for(int i = idx - 1; i >= 0; i--){
		int l = mx, r = d - i;
		for(int j = l; j <= r; j++){
			dp[lay[i]][j] = dp[lay[i]][j] * w % L;
		}
		mx = r;
	}
}

int qry(int x){
	int ret = h[x];
	for(int i = 0; i < D && x > 0; i++){
		ret = ret * dp[x][i] % L;
		x = p[x];
	}
	return ret;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	for(int i = 0; i < N; i++) for(int j = 0; j < D; j++) dp[i][j] = 1;
	cin >> n >> L;
	for(int i = 0; i < n - 1; i++){
		int u, v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1);
	for(int i = 1; i <= n; i++) cin >> h[i];
	int q;
	cin >> q;
	for(int i = 0; i < q; i++){
		int t; cin >> t;
		if(t == 1){
			int x, d, w;
			cin >> x >> d >> w; 
			upd(x, d, w);
		}else{
			int x;
			cin >> x;
			cout << qry(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