oj.uz

Submission #677982

# Submission time Handle Problem Language Result Execution time Memory
677982 2023-01-04T21:32:24 Z NK_ Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 44604 KB 
#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;
		dout << u << " " << v << endl;

		dout << "BEFORE" << endl;
		dout << v << " " << X[v] << endl;
		for(auto x : P[v]) dout << x << " ";
		dout << endl;
		for(auto x : R[v]) dout << x << " ";
		dout << endl; 	
		dout << u << " " << X[u] << endl;
		for(auto x : P[u]) dout << x << " ";
		dout << endl;
		for(auto x : R[u]) dout << x << " ";
		dout << endl; 	

		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);

		dout << "AFTER" << endl;
		dout << v << " " << X[v] << endl;
		for(auto x : P[v]) dout << x << " ";
		dout << endl;
		for(auto x : R[v]) dout << x << " ";
		dout << endl; 
	};


	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Execution timed out 1081 ms 2768 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Execution timed out 1084 ms 44604 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1087 ms 39804 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1091 ms 40088 KB Time limit exceeded
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 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Execution timed out 1081 ms 2768 KB Time limit exceeded
5 Halted 0 ms 0 KB -