Submission #888451

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888451	2023-12-17T12:46:34 Z	rorro	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	200 ms	50272 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 = 17;
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	16 ms	30044 KB	Output is correct
2	Correct	16 ms	30148 KB	Output is correct
3	Correct	15 ms	30044 KB	Output is correct
4	Correct	15 ms	30040 KB	Output is correct
5	Correct	16 ms	30028 KB	Output is correct
6	Correct	16 ms	30080 KB	Output is correct
7	Correct	15 ms	30044 KB	Output is correct
8	Correct	15 ms	30044 KB	Output is correct
9	Correct	15 ms	30044 KB	Output is correct
10	Correct	15 ms	30184 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	30044 KB	Output is correct
2	Correct	16 ms	30148 KB	Output is correct
3	Correct	15 ms	30044 KB	Output is correct
4	Correct	15 ms	30040 KB	Output is correct
5	Correct	16 ms	30028 KB	Output is correct
6	Correct	16 ms	30080 KB	Output is correct
7	Correct	15 ms	30044 KB	Output is correct
8	Correct	15 ms	30044 KB	Output is correct
9	Correct	15 ms	30044 KB	Output is correct
10	Correct	15 ms	30184 KB	Output is correct
11	Correct	16 ms	30044 KB	Output is correct
12	Correct	16 ms	30040 KB	Output is correct
13	Correct	16 ms	30040 KB	Output is correct
14	Correct	18 ms	30056 KB	Output is correct
15	Correct	16 ms	30044 KB	Output is correct
16	Correct	16 ms	30232 KB	Output is correct
17	Correct	15 ms	30232 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	30044 KB	Output is correct
2	Correct	16 ms	30148 KB	Output is correct
3	Correct	15 ms	30044 KB	Output is correct
4	Correct	15 ms	30040 KB	Output is correct
5	Correct	16 ms	30028 KB	Output is correct
6	Correct	16 ms	30080 KB	Output is correct
7	Correct	15 ms	30044 KB	Output is correct
8	Correct	15 ms	30044 KB	Output is correct
9	Correct	15 ms	30044 KB	Output is correct
10	Correct	15 ms	30184 KB	Output is correct
11	Correct	16 ms	30044 KB	Output is correct
12	Correct	16 ms	30040 KB	Output is correct
13	Correct	16 ms	30040 KB	Output is correct
14	Correct	18 ms	30056 KB	Output is correct
15	Correct	16 ms	30044 KB	Output is correct
16	Correct	16 ms	30232 KB	Output is correct
17	Correct	15 ms	30232 KB	Output is correct
18	Correct	21 ms	30556 KB	Output is correct
19	Correct	18 ms	30556 KB	Output is correct
20	Correct	18 ms	30556 KB	Output is correct
21	Correct	18 ms	30500 KB	Output is correct
22	Correct	18 ms	30556 KB	Output is correct
23	Correct	19 ms	30552 KB	Output is correct
24	Correct	18 ms	30500 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	30044 KB	Output is correct
2	Correct	16 ms	30148 KB	Output is correct
3	Correct	15 ms	30044 KB	Output is correct
4	Correct	15 ms	30040 KB	Output is correct
5	Correct	16 ms	30028 KB	Output is correct
6	Correct	16 ms	30080 KB	Output is correct
7	Correct	15 ms	30044 KB	Output is correct
8	Correct	15 ms	30044 KB	Output is correct
9	Correct	15 ms	30044 KB	Output is correct
10	Correct	15 ms	30184 KB	Output is correct
11	Correct	16 ms	30044 KB	Output is correct
12	Correct	16 ms	30040 KB	Output is correct
13	Correct	16 ms	30040 KB	Output is correct
14	Correct	18 ms	30056 KB	Output is correct
15	Correct	16 ms	30044 KB	Output is correct
16	Correct	16 ms	30232 KB	Output is correct
17	Correct	15 ms	30232 KB	Output is correct
18	Correct	21 ms	30556 KB	Output is correct
19	Correct	18 ms	30556 KB	Output is correct
20	Correct	18 ms	30556 KB	Output is correct
21	Correct	18 ms	30500 KB	Output is correct
22	Correct	18 ms	30556 KB	Output is correct
23	Correct	19 ms	30552 KB	Output is correct
24	Correct	18 ms	30500 KB	Output is correct
25	Correct	15 ms	29976 KB	Output is correct
26	Correct	18 ms	30556 KB	Output is correct
27	Correct	18 ms	30552 KB	Output is correct
28	Correct	19 ms	30556 KB	Output is correct
29	Correct	19 ms	30508 KB	Output is correct
30	Correct	19 ms	30300 KB	Output is correct
31	Correct	18 ms	30344 KB	Output is correct
32	Correct	18 ms	30440 KB	Output is correct
33	Correct	19 ms	30300 KB	Output is correct

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	30044 KB	Output is correct
2	Correct	16 ms	30148 KB	Output is correct
3	Correct	15 ms	30044 KB	Output is correct
4	Correct	15 ms	30040 KB	Output is correct
5	Correct	16 ms	30028 KB	Output is correct
6	Correct	16 ms	30080 KB	Output is correct
7	Correct	15 ms	30044 KB	Output is correct
8	Correct	15 ms	30044 KB	Output is correct
9	Correct	15 ms	30044 KB	Output is correct
10	Correct	15 ms	30184 KB	Output is correct
11	Correct	16 ms	30044 KB	Output is correct
12	Correct	16 ms	30040 KB	Output is correct
13	Correct	16 ms	30040 KB	Output is correct
14	Correct	18 ms	30056 KB	Output is correct
15	Correct	16 ms	30044 KB	Output is correct
16	Correct	16 ms	30232 KB	Output is correct
17	Correct	15 ms	30232 KB	Output is correct
18	Correct	21 ms	30556 KB	Output is correct
19	Correct	18 ms	30556 KB	Output is correct
20	Correct	18 ms	30556 KB	Output is correct
21	Correct	18 ms	30500 KB	Output is correct
22	Correct	18 ms	30556 KB	Output is correct
23	Correct	19 ms	30552 KB	Output is correct
24	Correct	18 ms	30500 KB	Output is correct
25	Incorrect	144 ms	50272 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	16 ms	30240 KB	Output is correct
2	Correct	15 ms	30212 KB	Output is correct
3	Correct	192 ms	40936 KB	Output is correct
4	Correct	200 ms	41112 KB	Output is correct
5	Correct	189 ms	40884 KB	Output is correct

Subtask #7
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	30044 KB	Output is correct
2	Correct	16 ms	30148 KB	Output is correct
3	Correct	15 ms	30044 KB	Output is correct
4	Correct	15 ms	30040 KB	Output is correct
5	Correct	16 ms	30028 KB	Output is correct
6	Correct	16 ms	30080 KB	Output is correct
7	Correct	15 ms	30044 KB	Output is correct
8	Correct	15 ms	30044 KB	Output is correct
9	Correct	15 ms	30044 KB	Output is correct
10	Correct	15 ms	30184 KB	Output is correct
11	Correct	16 ms	30044 KB	Output is correct
12	Correct	16 ms	30040 KB	Output is correct
13	Correct	16 ms	30040 KB	Output is correct
14	Correct	18 ms	30056 KB	Output is correct
15	Correct	16 ms	30044 KB	Output is correct
16	Correct	16 ms	30232 KB	Output is correct
17	Correct	15 ms	30232 KB	Output is correct
18	Correct	21 ms	30556 KB	Output is correct
19	Correct	18 ms	30556 KB	Output is correct
20	Correct	18 ms	30556 KB	Output is correct
21	Correct	18 ms	30500 KB	Output is correct
22	Correct	18 ms	30556 KB	Output is correct
23	Correct	19 ms	30552 KB	Output is correct
24	Correct	18 ms	30500 KB	Output is correct
25	Correct	15 ms	29976 KB	Output is correct
26	Correct	18 ms	30556 KB	Output is correct
27	Correct	18 ms	30552 KB	Output is correct
28	Correct	19 ms	30556 KB	Output is correct
29	Correct	19 ms	30508 KB	Output is correct
30	Correct	19 ms	30300 KB	Output is correct
31	Correct	18 ms	30344 KB	Output is correct
32	Correct	18 ms	30440 KB	Output is correct
33	Correct	19 ms	30300 KB	Output is correct
34	Incorrect	144 ms	50272 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

Submission #888451

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