Submission #722146

#	Time	Username	Problem	Language	Result	Execution time	Memory
722146		gagik_2007	Stranded Far From Home (BOI22_island)	C++17	100 / 100	299 ms	45556 KiB

island

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll LG = 31;
ll n, m, k;
vector<ll>g[N];
ll a[N];
vector<ll>c[N];
ll p[N];
ll sz[N];
ll sum[N];
bool used[N];

void make_set(ll v) {
	p[v] = v;
	sz[v] = 1;
	sum[v] = a[v];
	c[v].push_back(v);
}

ll find_set(ll v) {
	if (p[v] == v)return v;
	return p[v] = find_set(p[v]);
}

void union_sets(ll v, ll u) {
	v = find_set(v);
	u = find_set(u);
	if (u != v) {
		if (sz[v] < sz[u]) {
			swap(v, u);
		}
		p[u] = v;
		sz[v] += sz[u];
		sum[v] += sum[u];
		sz[u] = 0;
		sum[u] = 0;
		if (c[v].size() < c[u].size()) {
			swap(c[v], c[u]);
		}
		for (ll x : c[u]) {
			c[v].push_back(x);
		}
		c[u].clear();
	}
}

priority_queue<pair<int, int>>deq;
bool used2[N];

string other_sol() {
	string ans = "";
	for (int u = 1; u <= n; u++) {
		for (int v = 1; v <= n; v++) {
			used2[v] = false;
		}
		while (!deq.empty()) {
			deq.pop();
		}
		used2[u] = true;
		ll cur = a[u];
		bool ok = true;
		for (int to : g[u]) {
			if (!used2[to]) {
				deq.push({ -a[to],to });
				used2[to] = true;
			}
		}
		while (!deq.empty()) {
			int v = deq.top().ss;
			deq.pop();
			if (a[v] > cur) {
				//cout << v << " " << a[v] << " " << cur << endl;
				ok = false;
				break;
			}
			cur += a[v];
			for (int to : g[v]) {
				if (!used2[to]) {
					deq.push({ -a[to],to });
					used2[to] = true;
				}
			}
		}
		for (int v = 1; v <= n; v++) {
			if (!used2[v]) {
				//cout << v << " " << "CHMTAV\n";
				ok = false;
				break;
			}
		}
		ans += ok + '0';
	}
	return ans;
}

string main_sol() {
	vector<ll>vs;
	ll summ = 0;
	for (ll i = 1; i <= n; i++) {
		make_set(i);
		summ += a[i];
		vs.push_back(i);
	}
	auto comp = [](ll x, ll y) {
		return a[x] < a[y];
	};
	sort(vs.begin(), vs.end(), comp);
	ll i = 0;
	ll cur = a[vs[i]];
	//cout << "OK" << endl;
	while (i < n) {
		ll j = i;
		while (i < n && a[vs[i]] == cur) {
			for (ll to : g[vs[i]]) {
				if (a[to] <= cur) {
					int papa = find_set(to);
					if (sum[papa] < a[vs[i]]) {
						for (int x : c[papa]) {
							used[x] = true;
						}
						c[papa].clear();
					}
					union_sets(vs[i], to);
				}
			}
			//cout << i << endl;
			i++;
		}
		cur = (i < n ? a[vs[i]] : summ);
	}
	string ans = "";
	if (sz[find_set(1)] != n) {
		for (ll i = 1; i <= n; i++) {
			ans += '0';
		}
	}
	else {
		for (ll i = 1; i <= n; i++) {
			ans += !used[i] + '0';
		}
	}
	return ans;
}

int main() {
	//freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	cin >> n >> m;
	for (ll i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (ll i = 0; i < m; i++) {
		ll x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	string r1 = main_sol();
	cout << r1 << endl;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Compilation message (stderr)

island.cpp: In function 'std::string main_sol()':
island.cpp:142:6: warning: unused variable 'j' [-Wunused-variable]
  142 |   ll j = i;
      |      ^

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