oj.uz

Submission #868059

# Submission time Handle Problem Language Result Execution time Memory
868059 2023-10-30T10:41:23 Z TAhmed33 Stranded Far From Home (BOI22_island) C++
40 / 100
 1000 ms 50088 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 25;
vector <int> adj2[MAXN];
vector <int> adj[MAXN];
bool ok[MAXN];
set <int> pp;
int cnt[MAXN];
bool vis[MAXN];
int sum = 0;
vector <int> cur;
int y;
void dfs (int pos) {
	vis[pos] = 1; sum += cnt[pos]; cur.push_back(pos);
	for (auto j : adj[pos]) if (!vis[j] && cnt[j] <= y) dfs(j);
}
signed main () {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> cnt[i];
		pp.insert(cnt[i]);
	}
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		adj2[a].push_back(b);
		adj2[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) ok[i] = 1;
	int z = pp.size();
	for (int l = 0; l + 1 < z; l++) {
		auto i = *(pp.begin()); pp.erase(i); y = i;
		if (pp.empty()) break;
		for (int j = 1; j <= n; j++) {
			for (auto k : adj2[j]) {
				if (cnt[j] == i || cnt[k] == i) {
					adj[k].push_back(j);
					adj[j].push_back(k);
				}
			}
		}
		memset(vis, 0, sizeof(vis));
		for (int j = 1; j <= n; j++) {
			if (!vis[j] && cnt[j] <= y) {
				sum = 0; cur.clear();
				dfs(j);
				if (sum < *(pp.begin())) {
					for (auto l : cur) {
						ok[l] = 0;
					}
				}
			}
		}
	}	
	for (int i = 1; i <= n; i++) cout << ok[i];
	cout << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 3 ms 11612 KB Output is correct
3 Correct 2 ms 11612 KB Output is correct
4 Correct 82 ms 12016 KB Output is correct
5 Correct 85 ms 12152 KB Output is correct
6 Correct 4 ms 11864 KB Output is correct
7 Correct 66 ms 12112 KB Output is correct
8 Correct 55 ms 11864 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 51 ms 12096 KB Output is correct
11 Correct 65 ms 12116 KB Output is correct
12 Correct 39 ms 12380 KB Output is correct
13 Correct 4 ms 11864 KB Output is correct
14 Correct 11 ms 11868 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 3 ms 11612 KB Output is correct
3 Execution timed out 1083 ms 28464 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 537 ms 35908 KB Output is correct
3 Correct 446 ms 40560 KB Output is correct
4 Correct 493 ms 40164 KB Output is correct
5 Correct 200 ms 23676 KB Output is correct
6 Correct 198 ms 23100 KB Output is correct
7 Correct 216 ms 37052 KB Output is correct
8 Correct 188 ms 46688 KB Output is correct
9 Correct 261 ms 36684 KB Output is correct
10 Correct 231 ms 35012 KB Output is correct
11 Correct 320 ms 50088 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 3 ms 11612 KB Output is correct
3 Correct 2 ms 11612 KB Output is correct
4 Correct 82 ms 12016 KB Output is correct
5 Correct 85 ms 12152 KB Output is correct
6 Correct 4 ms 11864 KB Output is correct
7 Correct 66 ms 12112 KB Output is correct
8 Correct 55 ms 11864 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 51 ms 12096 KB Output is correct
11 Correct 65 ms 12116 KB Output is correct
12 Correct 39 ms 12380 KB Output is correct
13 Correct 4 ms 11864 KB Output is correct
14 Correct 11 ms 11868 KB Output is correct
15 Correct 2 ms 11612 KB Output is correct
16 Correct 3 ms 11612 KB Output is correct
17 Execution timed out 1083 ms 28464 KB Time limit exceeded
18 Halted 0 ms 0 KB -