제출 #677983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677983		NK_	Stranded Far From Home (BOI22_island)	C++17	100 / 100	294 ms	53988 KiB

island

#include <bits/stdc++.h>

using namespace std;

#ifdef DLOCAL
	#define dout cout
#else 
	#define dout cerr
#endif

using ll = long long;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;
	vector<int> A(N); for(auto& x : A) cin >> x;

	vector<vector<int>> adj(N);

	for(int i = 0; i < M; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	vector<int> ord(N); iota(begin(ord), end(ord), 0);
	sort(begin(ord), end(ord), [&](int x, int y) {
		return A[x] < A[y];
	});

	string ans(N, '1');

	vector<ll> X(N);
	vector<int> ID(N);
	vector<vector<int>> P(N), R(N);

	for(int i = 0; i < N; i++) {
		X[i] = A[i];
		ID[i] = i;
		P[i] = R[i] = {i};
	}


	auto merge = [&](int u, int v) {
		u = ID[u], v = ID[v];
		if (u == v) return;

		if (size(P[u]) > size(P[v])) swap(u, v);

		for(auto x : P[u]) {
			P[v].push_back(x);
			X[v] += A[x];
			ID[x] = v;
		}

		for(auto x : R[u]) R[v].push_back(x);
	};


	for(auto u : ord) {
		for(auto v : adj[u]) {
			if (A[v] > A[u]) continue;
			int V = ID[v];
			if (X[V] < A[u]) {
				for(auto x : R[V]) ans[x] = '0';
				R[V] = {};
			}
			merge(v, u);
		}
	}


	cout << ans << endl;

	return 0;
}

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