oj.uz

Submission #572838

# Submission time Handle Problem Language Result Execution time Memory
572838 2022-06-05T11:12:54 Z ritul_kr_singh Stranded Far From Home (BOI22_island) C++17
0 / 100
 181 ms 29640 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;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	sort(byS, byS + N);

	for(auto [cur, r] : byS) {
		int u = find(r);
		for(int &v : g[r]) if(s[v] <= cur) {
			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(s[v] <= cur && 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 5 ms 9812 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Incorrect 181 ms 29620 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 5 ms 9812 KB Output isn't correct
5 Halted 0 ms 0 KB -