Submission #888452

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888452	2023-12-17T12:48:28 Z	rorro	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	194 ms	47484 KB

Main

#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

#define ll long long
#define lld long double
#define st first
#define nd second
#define mp make_pair
#define ii pair<int, int>
#define vll vector<ll>
#define vi vector<int>
#define vvi vector<vector<int> >
#define pb push_back
#define eb emplace_back
#define remax(a, b) a = max(a, b);
#define remin(a, b) a = min(a, b);
#define all(x) x.begin(), x.end()
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bit(n, x) (n & (1 << x))
#define rep(a, b) for(int a = 0; a < b; ++a)

using namespace std;

const int maxn = 2e5;
const int maxlog = 18;
vvi up(maxn, vi(maxlog));
vvi g(maxn);
vi par(maxn);
vi sz(maxn, 1);
vi depth(maxn);
vi ans(maxn, 0);
vi h(maxn);
vi mx(maxn); //vertex, h[mx[find_(v)]] to max h w spojnej z v

void dfs(int cur, int pare) {
	depth[cur] = depth[pare]+1;
	up[cur][0] = pare;
	for (int i = 1; i < maxlog; ++i) up[cur][i] = up[up[cur][i-1]][i-1];
	for (int u : g[cur]) {
		if (u != pare) {
			dfs(u, cur);
		}
	}
}

int dist(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v); //u jest glebiej niz v
	int dt = depth[u]-depth[v];
	for (int i = maxlog-1; i >= 0; --i) {
		if (depth[up[u][i]] >= depth[v]) u = up[u][i]; //{cout << "hi " << u << endl; u = up[u][i];}
	}
	//teraz sa tak samo gleboko
	if (u == v) return dt;
	//teraz sa rozne, i na tej samej glebokosci
	for (int i = maxlog-1; i >= 0; --i) {
		if (up[u][i] != up[v][i]) {
			u = up[u][i], v = up[v][i];
			dt += (1<<(1+i));
		}
	}
	return dt + 2;
}

int find_(int a) {
	if (a == par[a]) return a;
	return par[a] = find_(par[a]);
}

void join_(int a, int b) {
	a = find_(a), b = find_(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a, b);
	sz[a] += sz[b];
	//remax(mx[a], h[mx[b]]);
	if (h[mx[a]] < h[mx[b]]) mx[a] = mx[b];
	remax(ans[a], ans[b]);
	par[b] = a;
}

int main() {
	fastio();
	iota(all(par), 0), iota(all(mx), 0);
	int n;
	cin >> n;
	vector<ii> q(n);
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
		q[i] = mp(h[i], i);
	}
	sort(all(q));
	for (int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		--a;--b;
		g[a].eb(b);
		g[b].eb(a);
	}
	depth[0] = -1;
	dfs(0, 0);
	/*rep(i, n) {
		rep(j, n) {
			cout << "i: " << i << " j: " << j << " d[i]: " << depth[i] << " d[j]: " << depth[j] << endl;
			cout << "dist: " << dist(i, j) << endl;
		}
	}*/
	for (int i = 0; i < n; ++i) {
		const int cur = q[i].nd, curh = q[i].st;
		for (int u : g[cur]) {
			if (h[u] < curh) {
				u = find_(u);
				//remax(ans[u], ans[u]+dist(mx[u], cur));
				ans[u] += dist(mx[u], cur);
				join_(cur, u);
			}
		}
	}
	cout << ans[find_(0)] << '\n'; //+dist(n-1, q[n-1].nd) << '\n';


	return 0;
}

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	30040 KB	Output is correct
2	Correct	15 ms	30104 KB	Output is correct
3	Correct	14 ms	30044 KB	Output is correct
4	Correct	15 ms	30044 KB	Output is correct
5	Correct	15 ms	30044 KB	Output is correct
6	Correct	15 ms	30040 KB	Output is correct
7	Correct	14 ms	30044 KB	Output is correct
8	Correct	14 ms	30044 KB	Output is correct
9	Correct	15 ms	30044 KB	Output is correct
10	Correct	15 ms	30044 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	30040 KB	Output is correct
2	Correct	15 ms	30104 KB	Output is correct
3	Correct	14 ms	30044 KB	Output is correct
4	Correct	15 ms	30044 KB	Output is correct
5	Correct	15 ms	30044 KB	Output is correct
6	Correct	15 ms	30040 KB	Output is correct
7	Correct	14 ms	30044 KB	Output is correct
8	Correct	14 ms	30044 KB	Output is correct
9	Correct	15 ms	30044 KB	Output is correct
10	Correct	15 ms	30044 KB	Output is correct
11	Correct	19 ms	30044 KB	Output is correct
12	Correct	19 ms	30100 KB	Output is correct
13	Correct	15 ms	30128 KB	Output is correct
14	Correct	16 ms	30044 KB	Output is correct
15	Correct	16 ms	30076 KB	Output is correct
16	Correct	19 ms	30044 KB	Output is correct
17	Correct	18 ms	30044 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	30040 KB	Output is correct
2	Correct	15 ms	30104 KB	Output is correct
3	Correct	14 ms	30044 KB	Output is correct
4	Correct	15 ms	30044 KB	Output is correct
5	Correct	15 ms	30044 KB	Output is correct
6	Correct	15 ms	30040 KB	Output is correct
7	Correct	14 ms	30044 KB	Output is correct
8	Correct	14 ms	30044 KB	Output is correct
9	Correct	15 ms	30044 KB	Output is correct
10	Correct	15 ms	30044 KB	Output is correct
11	Correct	19 ms	30044 KB	Output is correct
12	Correct	19 ms	30100 KB	Output is correct
13	Correct	15 ms	30128 KB	Output is correct
14	Correct	16 ms	30044 KB	Output is correct
15	Correct	16 ms	30076 KB	Output is correct
16	Correct	19 ms	30044 KB	Output is correct
17	Correct	18 ms	30044 KB	Output is correct
18	Correct	19 ms	30552 KB	Output is correct
19	Correct	17 ms	30620 KB	Output is correct
20	Correct	17 ms	30552 KB	Output is correct
21	Correct	17 ms	30556 KB	Output is correct
22	Correct	17 ms	30520 KB	Output is correct
23	Correct	18 ms	30564 KB	Output is correct
24	Correct	19 ms	30660 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	30040 KB	Output is correct
2	Correct	15 ms	30104 KB	Output is correct
3	Correct	14 ms	30044 KB	Output is correct
4	Correct	15 ms	30044 KB	Output is correct
5	Correct	15 ms	30044 KB	Output is correct
6	Correct	15 ms	30040 KB	Output is correct
7	Correct	14 ms	30044 KB	Output is correct
8	Correct	14 ms	30044 KB	Output is correct
9	Correct	15 ms	30044 KB	Output is correct
10	Correct	15 ms	30044 KB	Output is correct
11	Correct	19 ms	30044 KB	Output is correct
12	Correct	19 ms	30100 KB	Output is correct
13	Correct	15 ms	30128 KB	Output is correct
14	Correct	16 ms	30044 KB	Output is correct
15	Correct	16 ms	30076 KB	Output is correct
16	Correct	19 ms	30044 KB	Output is correct
17	Correct	18 ms	30044 KB	Output is correct
18	Correct	19 ms	30552 KB	Output is correct
19	Correct	17 ms	30620 KB	Output is correct
20	Correct	17 ms	30552 KB	Output is correct
21	Correct	17 ms	30556 KB	Output is correct
22	Correct	17 ms	30520 KB	Output is correct
23	Correct	18 ms	30564 KB	Output is correct
24	Correct	19 ms	30660 KB	Output is correct
25	Correct	15 ms	30044 KB	Output is correct
26	Correct	18 ms	30308 KB	Output is correct
27	Correct	18 ms	30556 KB	Output is correct
28	Correct	18 ms	30300 KB	Output is correct
29	Correct	18 ms	30456 KB	Output is correct
30	Correct	19 ms	30300 KB	Output is correct
31	Correct	19 ms	30244 KB	Output is correct
32	Correct	18 ms	30552 KB	Output is correct
33	Correct	18 ms	30300 KB	Output is correct

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	30040 KB	Output is correct
2	Correct	15 ms	30104 KB	Output is correct
3	Correct	14 ms	30044 KB	Output is correct
4	Correct	15 ms	30044 KB	Output is correct
5	Correct	15 ms	30044 KB	Output is correct
6	Correct	15 ms	30040 KB	Output is correct
7	Correct	14 ms	30044 KB	Output is correct
8	Correct	14 ms	30044 KB	Output is correct
9	Correct	15 ms	30044 KB	Output is correct
10	Correct	15 ms	30044 KB	Output is correct
11	Correct	19 ms	30044 KB	Output is correct
12	Correct	19 ms	30100 KB	Output is correct
13	Correct	15 ms	30128 KB	Output is correct
14	Correct	16 ms	30044 KB	Output is correct
15	Correct	16 ms	30076 KB	Output is correct
16	Correct	19 ms	30044 KB	Output is correct
17	Correct	18 ms	30044 KB	Output is correct
18	Correct	19 ms	30552 KB	Output is correct
19	Correct	17 ms	30620 KB	Output is correct
20	Correct	17 ms	30552 KB	Output is correct
21	Correct	17 ms	30556 KB	Output is correct
22	Correct	17 ms	30520 KB	Output is correct
23	Correct	18 ms	30564 KB	Output is correct
24	Correct	19 ms	30660 KB	Output is correct
25	Incorrect	151 ms	47484 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #6
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	30044 KB	Output is correct
2	Correct	15 ms	30044 KB	Output is correct
3	Correct	194 ms	37928 KB	Output is correct
4	Correct	192 ms	38032 KB	Output is correct
5	Correct	193 ms	38224 KB	Output is correct

Subtask #7
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	30040 KB	Output is correct
2	Correct	15 ms	30104 KB	Output is correct
3	Correct	14 ms	30044 KB	Output is correct
4	Correct	15 ms	30044 KB	Output is correct
5	Correct	15 ms	30044 KB	Output is correct
6	Correct	15 ms	30040 KB	Output is correct
7	Correct	14 ms	30044 KB	Output is correct
8	Correct	14 ms	30044 KB	Output is correct
9	Correct	15 ms	30044 KB	Output is correct
10	Correct	15 ms	30044 KB	Output is correct
11	Correct	19 ms	30044 KB	Output is correct
12	Correct	19 ms	30100 KB	Output is correct
13	Correct	15 ms	30128 KB	Output is correct
14	Correct	16 ms	30044 KB	Output is correct
15	Correct	16 ms	30076 KB	Output is correct
16	Correct	19 ms	30044 KB	Output is correct
17	Correct	18 ms	30044 KB	Output is correct
18	Correct	19 ms	30552 KB	Output is correct
19	Correct	17 ms	30620 KB	Output is correct
20	Correct	17 ms	30552 KB	Output is correct
21	Correct	17 ms	30556 KB	Output is correct
22	Correct	17 ms	30520 KB	Output is correct
23	Correct	18 ms	30564 KB	Output is correct
24	Correct	19 ms	30660 KB	Output is correct
25	Correct	15 ms	30044 KB	Output is correct
26	Correct	18 ms	30308 KB	Output is correct
27	Correct	18 ms	30556 KB	Output is correct
28	Correct	18 ms	30300 KB	Output is correct
29	Correct	18 ms	30456 KB	Output is correct
30	Correct	19 ms	30300 KB	Output is correct
31	Correct	19 ms	30244 KB	Output is correct
32	Correct	18 ms	30552 KB	Output is correct
33	Correct	18 ms	30300 KB	Output is correct
34	Incorrect	151 ms	47484 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

Submission #888452

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

Subtask #4 10.0 / 10.0

Subtask #5 0 / 20.0

Subtask #6 23.0 / 23.0

Subtask #7 0 / 26.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
7.0 / 7.0

Subtask #4
10.0 / 10.0

Subtask #5
0 / 20.0

Subtask #6
23.0 / 23.0

Subtask #7
0 / 26.0