oj.uz

Submission #572830

# Submission time Handle Problem Language Result Execution time Memory
572830 2022-06-05T11:04:10 Z ritul_kr_singh Stranded Far From Home (BOI22_island) C++17
25 / 100
 213 ms 33840 KB 
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define sp << ' ' <<
#define nl << '\n'

const int LIM = 2e5;

int N, M, s[LIM], e[LIM];
vector<int> g[LIM], h[LIM];

int find(int u) {
	return e[u] < 0 ? u : e[u] = find(e[u]);
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M;

	array<int, 2> byS[N];

	for(int i = 0; i < N; ++i) {
		cin >> s[i];
		e[i] = -1;
		h[i] = {i};
		byS[i] = {s[i], i};
	}
	for(int i = 0; i < M; ++i) {
		int u, v; cin >> u >> v;
		--u, --v;
		if(make_pair(s[u], u) < make_pair(s[v], v)) swap(u, v);
		g[u].push_back(v);
	}
	sort(byS, byS + N);

	for(auto [_, r] : byS) {
		int u = find(r);
		for(int &v : g[r]) {
			v = find(v);
			if(s[v] < s[u]) h[v].clear();
			if(size(h[v]) > size(h[u]))
				h[u].swap(h[v]);
		}
		for(int &v : g[r]) if(u != v) {
			for(int y : h[v]) h[u].push_back(y);
			s[u] += s[v];
			e[v] = u;
		}
	}

	for(int u : h[find(0)])
		s[u] = -1;
	for(int i = 0; i < N; ++i)
		cout << (s[i] < 0);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 6 ms 9900 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9724 KB Output is correct
3 Correct 125 ms 29116 KB Output is correct
4 Correct 127 ms 31760 KB Output is correct
5 Correct 179 ms 31296 KB Output is correct
6 Correct 141 ms 32392 KB Output is correct
7 Correct 145 ms 32320 KB Output is correct
8 Correct 139 ms 30636 KB Output is correct
9 Correct 117 ms 33600 KB Output is correct
10 Correct 80 ms 24380 KB Output is correct
11 Correct 167 ms 30612 KB Output is correct
12 Correct 143 ms 30356 KB Output is correct
13 Correct 120 ms 33396 KB Output is correct
14 Correct 127 ms 33292 KB Output is correct
15 Correct 151 ms 30616 KB Output is correct
16 Correct 82 ms 30400 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 181 ms 33504 KB Output is correct
3 Correct 187 ms 33840 KB Output is correct
4 Correct 157 ms 33460 KB Output is correct
5 Correct 118 ms 32900 KB Output is correct
6 Correct 200 ms 33720 KB Output is correct
7 Correct 152 ms 30728 KB Output is correct
8 Correct 156 ms 30636 KB Output is correct
9 Correct 88 ms 30424 KB Output is correct
10 Correct 120 ms 28028 KB Output is correct
11 Correct 149 ms 29604 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 213 ms 29336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 6 ms 9900 KB Output isn't correct
5 Halted 0 ms 0 KB -