Submission #852660

#	Time	Username	Problem	Language	Result	Execution time	Memory
852660		Trisanu_Das	Stranded Far From Home (BOI22_island)	C++17	100 / 100	170 ms	35648 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
 
int N, M, s[200005], e[200005];
vector<int> g[200005], h[200005];
 
int find(int u) {
	return e[u] < 0 ? u : e[u] = find(e[u]);
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M;
	array<int, 2> byS[N];
	for(int i = 0; i < N; ++i) {
		cin >> s[i];
		e[i] = -1;
		h[i] = {i};
		byS[i] = {s[i], i};
	}
	for(int i = 0; i < M; ++i) {
		int u, v; cin >> u >> v;
		--u, --v;
		if(make_pair(s[u], u) < make_pair(s[v], v)) swap(u, v);
		g[u].push_back(v);
	}
	sort(byS, byS + N);
	for(auto [piss, r] : byS) {
		int u = find(r);
		for(int &v : g[r]) {
			v = find(v);
			if(s[v] < s[u]) h[v].clear();
			if(size(h[v]) > size(h[u])) h[u].swap(h[v]);
		}
		for(int &v : g[r]) if((v = find(v)) != u) {
			for(int y : h[v]) h[u].push_back(y);
			s[u] += s[v];
			e[v] = u;
		}
	}
	for(int u : h[find(0)]) s[u] = -1;
	for(int i = 0; i < N; ++i) cout << (s[i] < 0);
}

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