Submission #583862

#	Time	Username	Problem	Language	Result	Execution time	Memory
583862		valerikk	Stranded Far From Home (BOI22_island)	C++17	100 / 100	355 ms	37560 KiB

island

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <iomanip>

using namespace std;

#define all(a) (a).begin(), (a).end()

using ll = long long;
using ld = long double;

const int N = 2e5 + 7;

int n;
int s[N];
vector<int> g[N];
int p[N];
ll sum[N];
vector<int> st[N];
int ans[N];

int get(int v) {
	return p[v] == v ? v : p[v] = get(p[v]);
}

void merge(int v, int u) {
	v = get(v);
	u = get(u);
	if (v == u) return;
	if (sum[v] > sum[u]) swap(v, u);
	p[v] = u;
	sum[u] += sum[v];
	for (int w : st[v]) {
		st[u].push_back(w);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int m;
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	while (m--) {
		int a, b;
		cin >> a >> b;
		--a;
		--b;
		g[a].push_back(b);
		g[b].push_back(a);
	}	
	for (int i = 0; i < n; ++i) {
		ans[i] = 1;
	}
	vector<pair<int, int>> by_s;
	for (int i = 0; i < n; ++i) {
		by_s.push_back({s[i], i});
	}
	sort(all(by_s));

	for (int i = 0, j = 0; i < n; i = j) {
		vector<int> vs;
		while (j < n && by_s[j].first == by_s[i].first) {
			vs.push_back(by_s[j].second);
			++j;
		}
		for (int v : vs) {
			p[v] = v;
			sum[v] = s[v];
			st[v] = {v};
			for (int u : g[v]) {
				if (s[u] >= s[v]) continue;
				u = get(u);
				if (sum[u] >= s[v]) continue;
				while (!st[u].empty()) {
					ans[st[u].back()] = 0;
					st[u].pop_back();
				}
			}
		}
		for (int v : vs) {
			for (int u : g[v]) {
				if (s[u] <= s[v]) merge(v, u);
			}
		}
	}

	for (int i = 0; i < n; ++i) {
		cout << ans[i];
	}
	cout << "\n";

	return 0;	
}

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