oj.uz

Submission #677981

# Submission time Handle Problem Language Result Execution time Memory
677981 2023-01-04T21:25:59 Z NK_ Stranded Far From Home (BOI22_island) C++17
0 / 100
 270 ms 79544 KB 
#include <bits/stdc++.h>

using namespace std;

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 (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] < X[u]) {
				for(auto x : R[V]) ans[x] = '0';
				R[V] = {};
			}
			merge(v, u);
		}
	}


	cout << ans << endl;

	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 444 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 270 ms 52140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 152 ms 79544 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -