Submission #778817

#	Time	Username	Problem	Language	Result	Execution time	Memory
778817		aZvezda	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	930 ms	102028 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef LOCAL
#define cerr if(false)cerr
#endif

const ll MAX_N = 2e5 + 10;
const ll MAX_D = 45;

ll cnt[MAX_N][MAX_D];
ll n;
ll L;
vector<ll> g[MAX_N];
ll par[MAX_N];
ll start[MAX_N];
	
void dfs(ll x, ll p) {
	par[x] = p;
	for(const auto it : g[x]) {
		if(it == p) { continue; }
		dfs(it, x);
	}
}

void upd(ll x, ll d, ll w) {
	if(d == 0) {
		cnt[x][d] = (cnt[x][d] * w) % L;
		return;
	}
	if(par[x] == 0) {
		upd(x, d - 1, w);		
		cnt[x][d] = (cnt[x][d] * w) % L;
	} else {
		upd(par[x], d - 1, w);
		cnt[x][d] = (cnt[x][d] * w) % L;
		cnt[x][d - 1] = (cnt[x][d - 1] * w) % L;
	}
}

ll ans(ll x) {
	ll ret = start[x];
	ll curr = x, d = 0;
	while(curr != 0 && d < MAX_D) {
		ret = (ret * cnt[curr][d]) % L;
		curr = par[curr];
		d ++;
	}
	return ret;
}

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

	cin >> n >> L;
	for(ll i = 0; i < n - 1; i ++) {
		ll a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(ll i = 1; i <= n; i ++) {
		cin >> start[i];
	}
	for(ll i = 0; i < MAX_N; i ++) {
		for(ll j = 0; j < MAX_D; j ++) {
			cnt[i][j] = 1;
		}
	}

	dfs(1, 0);
	ll q;
	cin >> q;
	while(q --) {
		ll t;
		cin >> t;
		if(t == 1) {
			ll x, d, w;
			cin >> x >> d >> w;
			upd(x, d, w);
		} else {
			ll x;
			cin >> x;
			cout << ans(x) << "\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