Submission #601300

#	Time	Username	Problem	Language	Result	Execution time	Memory
601300		patrikpavic2	Stranded Far From Home (BOI22_island)	C++17	0 / 100	1091 ms	14252 KiB

island

#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;
	S.clear();
	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 (stderr)

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35