oj.uz

Submission #601298

# Submission time Handle Problem Language Result Execution time Memory
601298 2022-07-21T15:50:13 Z patrikpavic2 Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 14372 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;
typedef vector < int > vi;
typedef long long ll;

const int N = 2e5 + 500;

vector < int > v[N];
int vel[N], bio[N], n, m;
set < pii > S;

bool check(int x){
	for(int i = 1;i <= n;i++) bio[i] = 0;
	ll sm = 0; S.insert({0, x}); bio[x] = 1;
	for(;(int)S.size() > 0 && S.begin() -> X <= sm;){
		int y = S.begin() -> Y;
		S.erase(S.begin());
		sm += vel[y];
		for(int z : v[y]){
			if(bio[z]) continue;
			bio[z] = 1; S.insert({vel[z], z});
		}
	}
	for(int i = 1;i <= n;i++)
		if(!bio[i]) return 0;
	return 1;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;i++)
		scanf("%d", vel + i);
	for(int i = 0;i < m;i++){
		int a, b; scanf("%d%d", &a, &b);
		v[a].PB(b), v[b].PB(a);
	}
	for(int i = 1;i <= n;i++)
		printf("%d", check(i));
	printf("\n");
	return 0;
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
island.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d", vel + i);
      |   ~~~~~^~~~~~~~~~~~~~~
island.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   int a, b; scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

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