Submission #1279758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279758		trideser	Stranded Far From Home (BOI22_island)	C++20	100 / 100	405 ms	27260 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<int> merged;
vector<int> killed;
set<pair<int, int>> to_be_killed;
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 i) {
	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;
	to_be_killed.erase(make_pair(dsu_sum[root_a], root_a));
	to_be_killed.erase(make_pair(dsu_sum[root_b], root_b));
	if(depth_a < depth_b) {
		merged[root_a] = i;
		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);
		to_be_killed.insert(make_pair(dsu_sum[root_b], root_b));
	}
	else {
		merged[root_b] = i;
		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);
		to_be_killed.insert(make_pair(dsu_sum[root_a], root_a));
	}
}


int32_t main() {
	cin >> N >> M;
	vector<int> people(N);
	merged = vector<int>(N, -1);
	killed = vector<int>(N, -2);
	dsu_parent = vector<int>(N, -1);
	dsu_depth = vector<int>(N, 0);
	for(int i = 0; i < N; i++) {
		cin >> people[i];
	}
	for(int i = 0; i < N; i++) {
		to_be_killed.insert(make_pair(people[i], 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
		while(!to_be_killed.empty() && to_be_killed.begin()->first < treshold) {
			killed[to_be_killed.begin()->second] = i;
			to_be_killed.erase(to_be_killed.begin());
		}

		while(i + 1 < M && get<0>(edges[i]) == get<0>(edges[i + 1])) {
			merge(get<1>(edges[i]), get<2>(edges[i]), i);
			i++;
		}
		merge(get<1>(edges[i]), get<2>(edges[i]), i);
	}
	for(int i = 0; i < N; i++) {
		bool alive = true;
		int last_merged = -1;
		int node = i;
		while(node != -1) {
			if(killed[node] > last_merged) alive = false;
			last_merged = max(last_merged, merged[node]);
			node = dsu_parent[node];
		}
		cout << alive;
	}
	return 0;
}

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