제출 #721407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721407		gagik_2007	Stranded Far From Home (BOI22_island)	C++17	0 / 100	244 ms	41316 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();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	vector<ll>vs;
	for (ll i = 1; i <= n; i++) {
		cin >> a[i];
		make_set(i);
		vs.push_back(i);
	}
	for (ll i = 0; i < m; i++) {
		ll x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	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]];
	while (i < n) {
		ll j = i;
		while (i < n && a[vs[i]] == cur) {
			for (ll to : g[vs[i]]) {
				if (a[to] <= cur) {
					union_sets(vs[i], to);
				}
			}
			i++;
		}
		ll nxt = (i < n ? a[vs[i]] : 0);
		while (j < n && a[vs[j]] == cur) {
			//cout << vs[j] << " " << sum[find_set(vs[j])] << endl;
			if (sum[find_set(vs[j])] < nxt) {
				//cout << vs[j] << endl;
				for (ll x : c[find_set(vs[j])]) {
					used[x] = true;
				}
				c[find_set(vs[j])].clear();
			}
			j++;
		}
		cur = nxt;
	}
	for (ll i = 1; i <= n; i++) {
		cout << !used[i];
	}
	cout << endl;
}

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

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