Submission #1192179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192179		franuch	Stranded Far From Home (BOI22_island)	C++20	10 / 100	389 ms	589824 KiB

island

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
const ll INF = 1e18;

struct DSU {
	ll k;
	vc<ll> par, rnk;
	DSU() = default;
	DSU(ll size) {
		k = size;
		par.assign(size, -1);
		rnk.assign(size, 0);
	}
	ll find(ll v) {
		if (par[v] == -1)
			return v;
		par[v] = find(par[v]);
		return par[v];
	}
	void onion(ll v, ll w) {
		ll x = find(v);
		ll y = find(w);
		if (x == y)
			return;
		k--;
		if (rnk[x] < rnk[y])
			par[x] = y;
		else if (rnk[x] > rnk[y])
			par[y] = x;
		else {
			par[x] = y;
			rnk[y]++;
		}
	}
};

ll V, E;
vc<ll> s;
vc<vc<ll>> g;
DSU dsu;
vc<vc<ll>> b;

void input() {
	cin >> V >> E;
	s.resize(V);
	for (ll &si : s)
		cin >> si;
	g.assign(V, vc<ll>());
	for (ll i = 0; i < E; i++) {
		ll v, w;
		cin >> v >> w;
		v--, w--;
		g[v].pub(w);
		g[w].pub(v);
	}
	for (ll v = 0; v < V; v++) {
		sort(all(g[v]));
		g[v].erase(unique(all(g[v])), g[v].end());
	}
}

void solve() {
	b.resize(V);
	for (ll v = 0; v < V; v++)
		b[v] = {v};
	vc<ll> ord(V);
	iota(all(ord), 0);
	sort(all(ord), [&](ll v, ll w) {
		return s[v] < s[w];
	});
	vc<ll> pos(V);
	for (ll i = 0; i < V; i++)
		pos[ord[i]] = i;
	dsu = DSU(V);
	
	for (ll v : ord) {
		ll sum = s[v];
		for (ll w : g[v]) {
			if (pos[w] > pos[v])
				continue;
			if (dsu.find(v) == dsu.find(w))
				continue;
			ll x = dsu.find(w);
			if (s[x] >= s[v]) {
				if (sz(b[x]) > sz(b[v]))
					swap(b[x], b[v]);
				for (ll u : b[x])
					b[v].pub(u);
			}
			b[x].clear();
			sum += s[x];
			s[x] = 0;
		}
		s[v] = sum;
		for (ll w : g[v])
			if (pos[w] < pos[v])
				dsu.onion(v, w);
		ll x = dsu.find(v);
		s[x] = s[v];
		b[x] = b[v];
		if (v != x) {
			s[v] = 0;
			b[v].clear();
		}
	}
	vc<bool> res(V, false);
	if (dsu.k == 1)
		for (ll v : b[dsu.find(0)])
			res[v] = true;
	for (ll v = 0; v < V; v++)
		cout << res[v];
	cout << "\n";
}

void program() {
	input();
	solve();
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	program();
	return 0;
}

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