Submission #1208377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208377		PenguinsAreCute	Sprinkler (JOI22_sprinkler)	C++17	38 / 100	2036 ms	90268 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
const int MAXD = 2;
int MOD;
struct fenwick {
	int n;
	vector<int> fw;
	fenwick(): n(MAXD+2), fw(MAXD+2,1) {}
	void up(int x, int u) {
		for(++x;x;x-=(x&(-x)))
			fw[x] = (1LL * fw[x] * u) % MOD;
	}
	int qry(int x) {
		int ans = 1;
		for(++x;x<n;x+=(x&(-x)))
			ans = (1LL * ans * fw[x]) % MOD;
		return ans;
	}
};
struct segwick {
	int n;
	vector<fenwick> seg;
	segwick() {}
	segwick(int _n): n(_n), seg(2*_n) {}
	void up(int l, int r, int x, int u) {
		for(l+=n,r+=n+1;l<r;l>>=1,r>>=1) {
			if(l&1)
				seg[l++].up(x, u);
			if(r&1)
				seg[--r].up(x, u);
		}
	}
	int qry(int x, int y) {
		int ans = 1;
		for(x+=n;x;x>>=1)
			ans = (1LL * ans * seg[x].qry(y)) % MOD;
		return ans;
	}
};

const int MAXN = 200'005;
vector<int> adj[MAXN];
int sub[MAXN], maxDist[MAXN], deg[MAXN];
pair<int,int> cent[MAXN];
int dfs0(int x, int p) {
	sub[x] = 1;
	for(auto i: adj[x])
		if(i != p && cent[i].first == -2)
			sub[x] += dfs0(i, x);
	return sub[x];
}
int dfs1(int x, int p, int n) {
	for(auto i: adj[x])
		if(i != p && cent[i].first == -2 && sub[i] > n / 2)
			return dfs1(i, x, n);
	return x;
}
void dfs2(int x, int p) {
	x = dfs1(x, p, dfs0(x, p));
	cent[x] = {p, deg[p]++};
	for(auto i: adj[x])
		if(cent[i].first == -2)
			dfs2(i, x);
}

int par[MAXN], h[MAXN], j[MAXN];
void dfs3(int x, int p) {
	par[x] = p;
	for(auto i: adj[x])
		if(i != p) {
			j[i] = (h[x]+h[j[j[x]]]==h[j[x]]*2?j[j[x]]:x);
			h[i] = h[x] + 1;
			dfs3(i, x);
		}
}
int t(int y, int x) {
	if(h[x] > h[y])
		swap(x, y);
	while(h[y] > h[x])
		y = (h[j[y]]<h[x]?par[y]:j[y]);
	while(x != y) {
		if(j[x] == j[y])
			x = par[x], y = par[y];
		else
			x = j[x], y = j[y];
	}
	return x;
}

int main() {
	int n;
	cin >> n >> MOD;
	for(int i=1,a,b;i<n;i++) {
		cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
	int s[n];
	for(int i=0;i<n;i++)
		cin >> s[i];

	fill(cent,cent+n,make_pair(-2,0));
	memset(maxDist,-1,sizeof(maxDist));
	dfs2(0,-1);
	dfs3(0,-1);
	segwick segw[n];
	for(int i=0;i<n;i++)
			segw[i] = segwick(deg[i] + 1);

	int q;
	cin >> q;
	while(q--) {
		int op;
		cin >> op;
		if(op == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			for(int y=--x,z=-1;~y;) {
				int cur = h[y] + h[x] - 2 * h[t(y,x)];
				if(d - cur >= 0) {
					if(~z) {
						segw[y].up(0,z-1,d-cur,w);
						segw[y].up(z+1,deg[y],d-cur,w);
					} else
						segw[y].up(0,deg[y],d-cur,w);
				}
				//maxDist[y] = max(maxDist[y], d - cur);
				z = cent[y].second;
				y = cent[y].first;
			}
		} else {
			int x;
			cin >> x;
			int ans = s[--x];
			for(int y=x,z=deg[y];~y;) {
				int cur = h[y] + h[x] - 2 * h[t(y,x)];
				if(~z)
					ans = 1LL * ans * segw[y].qry(z, cur) % MOD;
				/*
				if(maxDist[y] >= cur)
					ans = 0;
				*/
				z = cent[y].second;
				y = cent[y].first;
			}
			cout << ans << "\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