Submission #896810

#	Time	Username	Problem	Language	Result	Execution time	Memory
896810		TAhmed33	Sprinkler (JOI22_sprinkler)	C++98	12 / 100	1700 ms	52820 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e8;
const int MAXN = 2e5 + 25;
int h[MAXN], n, l, q;
vector <int> adj[MAXN];
struct LCA {
	int dep[MAXN], dp[18][MAXN];
	void dfs (int pos, int par) {
		dp[0][pos] = par;
		for (auto j : adj[pos]) {
			if (j != par) {
				dep[j] = 1 + dep[pos];
				dfs(j, pos);
			}
		}
	}
	int jump (int a, int b) {
		for (int i = 17; i >= 0; i--) {
			if (b & (1 << i)) {
				a = dp[i][a];
			}
		}
		return a;
	}
	int lca (int a, int b) {
		if (dep[a] > dep[b]) swap(a, b);
		b = jump(b, dep[b] - dep[a]);
		if (a == b) return a;
		for (int i = 17; i >= 0; i--) {
			int x = dp[i][a], y = dp[i][b];
			if (x && y && x != y) {
				a = x, b = y;
			}
		}
		return dp[0][a];
	}
	int dist (int a, int b) {
		return dep[a] + dep[b] - 2 * dep[lca(a, b)];
	}
	void init () {
		dfs(1, 0);
		for (int i = 1; i < 18; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = dp[i - 1][dp[i - 1][j]];
			}
		}
	}
} cur;
int cur_ans[MAXN];
bool vis[MAXN];
int p[MAXN], sze[MAXN];
void calc (int pos, int par) {
	sze[pos] = 1;
	for (auto j : adj[pos]) {
		if (j != par && !vis[j]) {
			calc(j, pos);
			sze[pos] += sze[j];
		}
	}
}
int get (int pos, int par, int z) {
	for (auto j : adj[pos]) {
		if (j != par && !vis[j] && sze[j] > z / 2) {
			return get(j, pos, z);
		}
	}
	return pos;
}	
void construct (int pos, int par) {
	calc(pos, -1);
	int c = get(pos, -1, sze[pos]);
	p[c] = par;
	//cout << c << " " << par << '\n';
	vis[c] = 1;
	for (auto j : adj[c]) {
		if (!vis[j]) {
			construct(j, c);
		}
	}
}
int main () {
	cin >> n >> l;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) cin >> h[i];
	cur.init();
	construct(1, 0);
	//for (int i = 1; i <= n; i++) cout << p[i] << " ";
//	cout << '\n';
	for (int i = 1; i <= n; i++) cur_ans[i] = inf;
	cin >> q;
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			cur_ans[x] = min(cur_ans[x], -d);
			int u = x;
			while (u != 0) {
				cur_ans[u] = min(cur_ans[u], cur_ans[x] + cur.dist(u, x));
				u = p[u];
			}
		} else {
			int x;
			cin >> x;
			int mn = inf;
			int u = x;
			while (u != 0) {
				mn = min(mn, cur_ans[u] + cur.dist(u, x));
				u = p[u];
			}
			cout << (mn <= 0 ? 0 : h[x]) << '\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