제출 #589276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589276		LastRonin	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	764 ms	79160 KiB

sprinkler

#pragma GCC optimize("O3")
 
#include <bits/stdc++.h> 
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
const int N = 2e5 + 60;
const int M = 5E5 + 100;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;
 
mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());
 
ll n, L, q, gl[N];
vector<int> g[N];
int dp[N];
int p[N], h[N];
int pr[N][41];

int mul(ll a, ll b) {	
	const ll z = L;
	return a * b % z;
}

void dfs(ll v, ll pr) {
	p[v] = pr;
	for(auto u : g[v]) {
		if(u == pr)continue;
		dfs(u, v);
	}

}

ll ans[M];
                        
ll t[M], A[M], b[M], c[M];
 
int main() {
	speed;
	cin >> n >> L;
	for(int i = 1, a, b; i < n; i++) {
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);		
	}
	for(int i = 1; i <= n; i++) {
		cin >> h[i];	
	}
	dfs(1, 0);
	p[1] = n + 1;
	for(int j = 1; j <= 40; j++) {
		p[n + j] = n + j + 1;		
	}
	for(int j = 1; j <= n; j++) {
		pr[j][0] = j;
		for(int i = 1; i <= 40; i++) {
			pr[j][i] = p[pr[j][i - 1]];
		}
	}
	cin >> q;
	for(int i = 1; i <= q; i++) {
		cin >> t[i] >> A[i];
		if(t[i] == 1)cin >> b[i] >> c[i];
		else ans[i] = 1;
	}
	for(int B = 40; B >= 0; B--) {
		for(int i = 1; i <= n + 40; i++) {
			dp[i] = 1;
		}
		for(int i = 1; i <= q; i++) {
			if(t[i] == 1 && b[i] != B)continue;
			int a = A[i];			
			if(t[i] == 1) {
				dp[a] = mul(dp[a], c[i]);
				b[i]--;
				A[i] = p[A[i]];
			} else {
				
				if(B != 0)
					ans[i] = mul(ans[i], dp[pr[a][B - 1]]);
				ans[i] = mul(ans[i], dp[pr[a][B]]);					
			}
		}
	}
	for(int i = 1; i <= q; i++) {
		if(t[i] == 2)cout << mul(h[A[i]], ans[i]) << "\n";
	}
}
/*
4 7
1 2
2 3
3 4
1 1 1 1
6
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
*/

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