Submission #1274746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274746		mdobric	Stranded Far From Home (BOI22_island)	C++20	0 / 100	3 ms	836 KiB

island

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

const int maxn = 200005;
int n, m;
long long s[maxn];
vector <int> v[maxn];
int parent[maxn], in[maxn], bio[maxn];
long long suma[maxn];
vector <int> dobri[maxn];
int ans[maxn];

int comp (int x, int y){
	if (s[x] < s[y]) return 1;
	return 0;
}

int find (int x){
	if (parent[x] == x) return x;
	return parent[x] = find(parent[x]);
}

void unite (int px, int py){
	if (dobri[px].size() < dobri[py].size()) swap(px, py);
	parent[py] = px;
	suma[px] += suma[py];
	for (int i = 0; i < dobri[py].size(); i++) dobri[px].push_back(dobri[py][i]);
	dobri[py].clear();
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> s[i];
		suma[i] = s[i];
		parent[i] = i;
		dobri[i].push_back(i);
		in[i] = i;
	}
	for (int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	sort(in, in + n, comp);
	for (int j = 0; j < n; j++){
		int x = in[j];
		bio[x] = 1;
		for (int i = 0; i < v[x].size(); i++){
			int y = v[x][i];
			if (bio[y] == 1){
				int px = find(x);
				int py = find(y);
				if (px != py){
					if (suma[py] < s[x]) dobri[py].clear();
					unite(px, py);
				}
			}
		}
		if (j == n - 1){
			int px = find(x);
			for (int i = 0; i < dobri[px].size(); i++) ans[dobri[px][i]] = 1;
		}
	}
	for (int i = 1; i <= n; i++) cout << ans[i];
	cout << "\n";

	return 0;
}

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