oj.uz

Submission #896810

# Submission time Handle Problem Language Result Execution time Memory
896810 2024-01-02T08:07:55 Z TAhmed33 Sprinkler (JOI22_sprinkler) C++
12 / 100
 1700 ms 52820 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 20828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 20828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 20828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20824 KB Output is correct
2 Correct 1638 ms 49748 KB Output is correct
3 Correct 1338 ms 46216 KB Output is correct
4 Correct 1491 ms 46816 KB Output is correct
5 Correct 1292 ms 35064 KB Output is correct
6 Correct 884 ms 36688 KB Output is correct
7 Correct 872 ms 38924 KB Output is correct
8 Correct 613 ms 39596 KB Output is correct
9 Correct 1700 ms 48976 KB Output is correct
10 Correct 1370 ms 52820 KB Output is correct
11 Correct 1405 ms 38360 KB Output is correct
12 Correct 1057 ms 38416 KB Output is correct
13 Correct 842 ms 40140 KB Output is correct
14 Correct 825 ms 40528 KB Output is correct
15 Correct 5 ms 20828 KB Output is correct
16 Correct 4 ms 20828 KB Output is correct
17 Correct 4 ms 20828 KB Output is correct
18 Correct 4 ms 20828 KB Output is correct
19 Correct 4 ms 20936 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 20824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 20828 KB Output isn't correct
2 Halted 0 ms 0 KB -