Submission #571906

#	Time	Username	Problem	Language	Result	Execution time	Memory
571906		8e7	Sprinkler (JOI22_sprinkler)	C++17	38 / 100	831 ms	276416 KiB

sprinkler

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define maxd 4
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int mod;
struct BIT{
	vector<vector<ll> > bit;
	int n;
	void init(int _n) {
		n = _n;
		bit.resize(maxd);
		for (int i = 0;i < maxd;i++) {
			bit[i].resize(n+1);
			for (int j = 1;j <= n;j++) bit[i][j] = 1;
		}
	}
	void modify(int ind, int d, int val) {
		//debug("mod", ind, d, val);
		ind++, d = maxd - 1 - d;
		for (;d < maxd;d += d & (-d)) {
			int tmp = ind;
			for (;ind <= n;ind += ind & (-ind)) bit[d][ind] = bit[d][ind] * val % mod;
			ind = tmp;
		}
	}	
	ll query(int ind, int d) {
		ind++, d = maxd - 1 - d;
		ll ret = 1;
		for (;d > 0;d -= d & (-d)) {
			int tmp = ind;
			for (;ind > 0;ind -= ind & (-ind)) ret = ret * bit[d][ind] % mod;
			ind = tmp;
		}
		return ret;
	}
} pref[maxn], suf[maxn];
vector<int> adj[maxn];
int par[maxn], pi[maxn], leaf[maxn];
void dfs(int n, int pa) {
	par[n] = pa;
	leaf[n] = 1;
	for (int v:adj[n]) {
		if (v != pa) {
			dfs(v, n);
			pi[v] = leaf[n]++;
		}
	}
	//debug(n, leaf[n]);
	pref[n].init(leaf[n]);
	suf[n].init(leaf[n]);
}
ll h[maxn];
void modify(int n, int d, int w) {
	int prv = 0;
	while (d >= 0 && n) {
		pref[n].modify(prv, d, w); 
		suf[n].modify(leaf[n] - 1 - prv, d, w); 
		prv = pi[n];
		n = par[n];
		d--;
	}
}
ll query(int n) {
	int cur = 0, prv = -1;
	ll ret = h[n];
	while (cur < maxd && n) {
		ret = (ret * pref[n].query(prv-1, cur) % mod * suf[n].query(leaf[n] - prv - 2, cur)%mod);
		prv = pi[n];
		n = par[n];
		cur++;
	}
	return ret;	
}
int main() {
	io
	int n;
	cin >> n >> mod;
	for (int i = 0;i < n - 1;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1;i <= n;i++) cin >> h[i]; 
	dfs(1, 0);
	int q;
	cin >> q;
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			modify(x, d, w);
		} else {
			int x;
			cin >> x;
			cout << query(x) << "\n";
		}
	}
}

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