Submission #1279707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279707		trideser	Stranded Far From Home (BOI22_island)	C++20	0 / 100	1 ms	572 KiB

island

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

#define int long long

vector<int> dsu_parent;
vector<int> dsu_sum;
int max_depth = 0;

pair<int, int> get_root(int node) {
	int depth = 0;
	while(dsu_parent[node] != -1) {
		depth++;
		max_depth = max(depth, max_depth);
		node = dsu_parent[node];
	}
	return make_pair(node, depth);
}

void merge(int a, int b) {
	int depth_a, depth_b, root_a, root_b;
	tie(root_a, depth_a) = get_root(a);
	tie(root_b, depth_b) = get_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;
	}
	else {
		dsu_parent[root_b] = root_a;
		dsu_sum[root_a] += dsu_sum[root_b];
		dsu_sum[root_b] = -1;
	}

}

int32_t main() {
	int N, M;
	cin >> N >> M;
	vector<int> people(N);
	dsu_parent = vector<int>(N, -1);
	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());
	vector<bool> alive(N, true);
	for(int i = 0; i < M; i++) {
		// kill nodes
		int treshold = get<0>(edges[i]);
		for(int j = 0; j < N; j++) {
			if(dsu_sum[get_root(j).first] < 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;
	cout << "\n" << max_depth;
	return 0;
}

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