oj.uz

Submission #725610

# Submission time Handle Problem Language Result Execution time Memory
725610 2023-04-17T18:20:08 Z WonderfulWhale Stranded Far From Home (BOI22_island) C++17
10 / 100
 226 ms 596 KB 
#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

vector<int> G[2009];
int tab[2009];
bool vis[2009];
int cnt;
bool ans[2009];

void bfs(int x) {
	priority_queue<pii, vector<pii>, greater<pii>> Q;
	vis[x] = true;
	Q.push({0, x});
	int sum = 0;
	while(sz(Q)&&Q.top().st<=sum) {
		cnt++;
		int y = Q.top().nd;
		Q.pop();
		sum += tab[y];
		for(int z:G[y]) {
			if(!vis[z]) {
				vis[z] = true;
				Q.push({tab[z], z});
			}
		}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	cin >> n >> m;
	for(int i=1;i<=n;i++) {
		cin >> tab[i];
	}
	for(int i=0;i<m;i++) {
		int a, b;
		cin >> a >> b;
		G[a].pb(b);
		G[b].pb(a);
	}
	for(int i=1;i<=n;i++) {
		cnt = 0;
		memset(vis, 0, sizeof(vis));
		bfs(i);
		if(cnt==n) ans[i] = true;
	}
	for(int i=1;i<=n;i++) cout << ans[i];
	cout << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 157 ms 468 KB Output is correct
5 Correct 147 ms 484 KB Output is correct
6 Correct 201 ms 484 KB Output is correct
7 Correct 152 ms 492 KB Output is correct
8 Correct 105 ms 484 KB Output is correct
9 Correct 226 ms 504 KB Output is correct
10 Correct 60 ms 468 KB Output is correct
11 Correct 57 ms 472 KB Output is correct
12 Correct 56 ms 492 KB Output is correct
13 Correct 105 ms 468 KB Output is correct
14 Correct 97 ms 472 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 3 ms 548 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 157 ms 468 KB Output is correct
5 Correct 147 ms 484 KB Output is correct
6 Correct 201 ms 484 KB Output is correct
7 Correct 152 ms 492 KB Output is correct
8 Correct 105 ms 484 KB Output is correct
9 Correct 226 ms 504 KB Output is correct
10 Correct 60 ms 468 KB Output is correct
11 Correct 57 ms 472 KB Output is correct
12 Correct 56 ms 492 KB Output is correct
13 Correct 105 ms 468 KB Output is correct
14 Correct 97 ms 472 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 456 KB Output is correct
17 Runtime error 2 ms 596 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -