Submission #911034

#	Time	Username	Problem	Language	Result	Execution time	Memory
911034		pragmatist	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1069 ms	17956 KiB

island

/*
JUDGE_ID : 331438IX
*/

#include<iostream>
#include<cassert>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<map>

using namespace std;

const int N = (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int MOD = (int)998244353;
const long long INF = (long long)1e18 + 7; 

int mult(int x, int y) {
	return 1ll*x*y%MOD;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) {
		x -= MOD;
	}
	return x;
}

int sub(int x, int y) {
	x -= y;
	if(x < 0) {
		x += MOD;
	}
	return x;
}

bool is_prime(int x) {
	if(x == 1) {
		return 0;
	}
	for(int i = 2; i * i <= x; ++i) {
		if(x % i == 0) {
			return 0;
		}
	}
	return 1;
}

int n, m, a[N];
vector<int> g[N];
bool used[N];

int main() {	
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);         
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for(int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}                         
	for(int s = 1; s <= n; ++s) {
		fill(used+1, used+1+n, 0);
		long long cur = a[s];
		priority_queue<pair<long long, int> > q;
		for(auto x : g[s]) {
			used[x] = 1;
			q.push({-a[x], x});
		}
		used[s] = 1;
		int cnt = 0;
		while(!q.empty()) {
			int v = q.top().second;
			q.pop();
			if(cur >= a[v]) {
				cnt++;
				cur += a[v];
				for(auto to : g[v]) {
					if(!used[to]) {
						used[to] = 1;
						q.push({-a[to], to});	
					}			
				}
			}			
		}
		cout << (cnt == n-1);
	}
	return 0;
}

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