Submission #1099008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099008		ohad	Stranded Far From Home (BOI22_island)	C++14	100 / 100	268 ms	28060 KiB

island

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
void init(ll n, vll& par) {
	for (ll i = 0; i < n; i++)
	{
		par[i] = i;
	}
}
ll find(ll a, vll& par) {
	if (par[a] == a)
		return a;
	return par[a] = find(par[a], par);
}

int main() {
	ll n, m;
	cin >> n >> m;
	vll num(n);
	for (auto& i : num)
	{
		cin >> i;
	}
	vector<vll> nei(n);
	for (int i = 0; i < m; i++)
	{
		ll a, b;
		cin >> a >> b;
		nei[a - 1].push_back(b - 1);
		nei[b - 1].push_back(a - 1);
	}
	vll par(n);
	vll overtake(n);
	init(n, par);
	init(n, overtake);
	vector<pair<ll, ll>> pairs;
	vll visited(n, 0);

	for (int i = 0; i < n; i++)
	{
		pairs.push_back({ num[i],i });
	}
	sort(pairs.begin(), pairs.end());

	for (int i = 0; i < n; i++)
	{
		ll v = pairs[i].second;
		ll cost = pairs[i].first;
		visited[v] = 1;
		for (int u : nei[v])
		{
			if (!visited[u])
				continue;
			u = find(u, par);
			if (u == v)
				continue;
			num[v] += num[u];
			par[u] = v;
			if (num[u] >= cost)
				overtake[u] = v;
		}
	}
	ll v = pairs[n - 1].second;
	for (int i = 0; i < n; i++)
	{
		if (find(i, overtake) == v)
			cout << 1;
		else
			cout << 0;
	}
	return 0;
}

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