Submission #1208351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208351		PenguinsAreCute	Sprinkler (JOI22_sprinkler)	C++17	12 / 100	1732 ms	32636 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200'005;
vector<int> adj[MAXN];
int sub[MAXN], cent[MAXN], maxDist[MAXN];
int dfs0(int x, int p) {
	sub[x] = 1;
	for(auto i: adj[x])
		if(i != p && cent[i] == -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] == -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;
	for(auto i: adj[x])
		if(cent[i] == -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, 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,-2);
	memset(maxDist,-1,sizeof(maxDist));
	dfs2(0,-1);
	dfs3(0,-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;~y;y=cent[y]) {
				int cur = h[y] + h[x] - 2 * h[t(y,x)];
				maxDist[y] = max(maxDist[y], d - cur);
			}
		} else {
			int x;
			cin >> x;
			int ans = s[--x];
			for(int y=x;~y;y=cent[y]) {
				int cur = h[y] + h[x] - 2 * h[t(y,x)];
				if(maxDist[y] >= cur)
					ans = 0;
			}
			cout << ans << "\n";
		}
	}
}

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