Submission #1208363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208363		PenguinsAreCute	Sprinkler (JOI22_sprinkler)	C++17	3 / 100	4098 ms	122584 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
struct fenwick {
	int n;
	vector<int> fw;
	fenwick(): n(42), fw(42,0) {}
	void up(int x, int u) {
		for(++x;x;x-=(x&(-x)))
			fw[x] += u;
	}
	int qry(int x) {
		int ans = 0;
		for(++x;x<n;x+=(x&(-x)))
			ans += fw[x];
		return ans;
	}
};
const int MAXN = 200'005;
vector<int> adj[MAXN];
int sub[MAXN], maxDist[MAXN], deg[MAXN];
pair<int,int> cent[MAXN];
vector<fenwick> fenw[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 exp(int a, int b, int l) {return (b?1LL * exp(1LL * a * a % l, b / 2, l) * (b & 1 ? a : 1) % l:1);}
int main() {
	int n, l;
	cin >> n >> l;
	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);
	for(int i=0;i<n;i++)
			fenw[i].resize(deg[i] + 1);

	int q;
	cin >> q;
	while(q--) {
		int op;
		cin >> op;
		if(op == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			x--;
			for(int y=0;y<n;y++)
					if(h[x] + h[y] - 2 * h[t(y,x)] <= d)
							s[y] = (1LL * s[y] * w) % l;
		} else {
			int x;
			cin >> x;
			cout << s[x-1] << "\n";
		}
	}
}

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