제출 #1274408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274408		altern23	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	585 ms	93372 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 2e5;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

void add(ll &a, ll b) { a = (a + b) % MOD; }
void sub(ll &a, ll b) { a = (a - b + MOD) % MOD; }
void mul(ll &a, ll b) { a = a * b % MOD; }

ll up[MAXN + 5], H[MAXN + 5];
ll dp[MAXN + 5][45];

vector<ll> adj[MAXN + 5];

void dfs(ll idx, ll par){
	up[idx] = par;
	for(auto i : adj[idx]){
		if(i != par) dfs(i, idx);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N, L; cin >> N >> L;
		for(int i = 2; i <= N; i++){
			ll u, v; cin >> u >> v;
			adj[u].push_back(v), adj[v].push_back(u);
		}
		
		dfs(1, 0);
		
		for(int i = 1; i <= N; i++){
			cin >> H[i];
			for(int j = 0; j <= 40; j++) dp[i][j] = 1LL;
		}
		
		ll Q; cin >> Q;
		for(int i = 1; i <= Q; i++){
			ll t; cin >> t;
			if(t == 1){
				ll idx, D, val; cin >> idx >> D >> val;
				for(;idx && D >= 0;){
					dp[idx][D] = dp[idx][D] * val % L;
					D--;
					idx = up[idx];
				}
			}
			else{
				ll idx; cin >> idx;
				ll ans = H[idx];
				for(int dep = 0; dep <= 40 && idx; dep++, idx = up[idx]){
					if(idx == 1){
						for(int j = dep; j <= 40; j++) ans = ans * dp[idx][j] % L;
						break;
					}
					ans = ans * dp[idx][dep] % L;
					if(dep + 1 <= 40) ans = ans * dp[idx][dep + 1] % L;
				}
				
				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