Submission #1130879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130879		nguyenkhangninh99	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	2166 ms	179744 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn = 2e5 + 69;

vector<int> g[maxn];

int mod;

int h[maxn], par[maxn];
int f[maxn][100];

void dfs(int u){
	for(int v: g[u]){
		if(v != par[u]){
			par[v] = u;
			dfs(v);
		}
	}
}
void solve(){
	int n; cin >> n >> mod;

	for(int i = 1; i <= n - 1; i++){
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = n + 1; i <= n + 40; i++) g[i].push_back(i + 1);
    g[n + 41].push_back(1);
	dfs(n + 1);
	for(int i = 0; i < maxn; i++){
		for(int j = 0; j < 100; j++) f[i][j] = 1;
	}

	int q; cin >> q;

	while(q--){
		int type; cin >> type;
		if(type == 1){
			int u, d, w; cin >> u >> d >> w;
			while(d >= 0){
                f[u][d] = (f[u][d] *= w) %= mod;
                if(d && u) f[u][d - 1] = (f[u][d - 1] *= w) %= mod;
                u = par[u];
                d--;
            }
		}

		else{
			int u; cin >> u;
			int res = h[u];
        	for (int d = 0; d <= 40; d++) res = (res * f[u][d]) % mod, u = par[u];
        	cout << res << "\n";
		}
		
	}
}

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

	solve();
}

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