Submission #1279741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279741		trideser	Stranded Far From Home (BOI22_island)	C++20	40 / 100	1096 ms	11400 KiB

island

#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> dsu_parent;
vector<int> dsu_sum;
vector<int> dsu_depth;
vector<bool> alive;
int N, M;
int max_depth = 0;
int sum_depth = 0;
int groot = 0;

int get_root(int node) {
	int depth = 0;
	while(dsu_parent[node] != -1) {
		depth++;
		node = dsu_parent[node];
	}
	max_depth = max(depth, max_depth);
	sum_depth += max(depth, max_depth);
	groot++;
	return node;
}

void merge(int a, int b) {
	int depth_a, depth_b, root_a, root_b;
	root_a = get_root(a);
	root_b = get_root(b);
	depth_a = dsu_depth[root_a];
	depth_b = dsu_depth[root_b];
	if(root_a == root_b) return;
	if(depth_a < depth_b) {
		dsu_parent[root_a] = root_b;
		dsu_sum[root_b] += dsu_sum[root_a];
		dsu_sum[root_a] = -1;
		dsu_depth[root_b] = max(dsu_depth[root_b], dsu_depth[root_a] + 1);
	}
	else {
		dsu_parent[root_b] = root_a;
		dsu_sum[root_a] += dsu_sum[root_b];
		dsu_sum[root_b] = -1;
		dsu_depth[root_a] = max(dsu_depth[root_a], dsu_depth[root_b] + 1);
	}
}


int32_t main() {
	cin >> N >> M;
	vector<int> people(N);
	alive = vector<bool>(N, true);
	dsu_parent = vector<int>(N, -1);
	dsu_depth = vector<int>(N, 0);
	for(int i = 0; i < N; i++) {
		cin >> people[i];
	}
	dsu_sum = people;
	vector<tuple<int, int, int>> edges(M);
	for(int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		edges[i] = make_tuple(max(people[a], people[b]), a, b);
	}
	sort(edges.begin(), edges.end());
	for(int i = 0; i < M; i++) {
		int treshold = get<0>(edges[i]);
		// kill
		for(int j = 0; j < N; j++) {
			if(dsu_sum[get_root(j)] < treshold) {
				alive[j] = false;
			}
		}

		while(i + 1 < M && get<0>(edges[i]) == get<0>(edges[i + 1])) {
			merge(get<1>(edges[i]), get<2>(edges[i]));
			i++;
		}
		merge(get<1>(edges[i]), get<2>(edges[i]));
	}
	for(bool b : alive) cout << b;
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 30 / 30
• Subtask 5: 0 / 35