Submission #721406

#	Time	Username	Problem	Language	Result	Execution time	Memory
721406		gagik_2007	Stranded Far From Home (BOI22_island)	C++17	0 / 100	236 ms	37548 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<int>g[N];
ll a[N];
vector<int>c[N];
ll p[N];
ll sz[N];
ll sum[N];
bool used[N];

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

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

void union_sets(int v, int 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 (int 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<int>vs;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		make_set(i);
		vs.push_back(i);
	}
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	auto comp = [](int x, int y) {
		return a[x] < a[y];
	};
	sort(vs.begin(), vs.end(), comp);
	int i = 0;
	int cur = a[vs[i]];
	while (i < n) {
		int j = i;
		while (i < n && a[vs[i]] == cur) {
			for (int to : g[vs[i]]) {
				if (a[to] <= cur) {
					union_sets(vs[i], to);
				}
			}
			i++;
		}
		int 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 (int x : c[find_set(vs[j])]) {
					used[x] = true;
				}
				c[find_set(vs[j])].clear();
			}
			j++;
		}
		cur = nxt;
	}
	for (int 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