Submission #1270833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270833		trideser	Stranded Far From Home (BOI22_island)	C++20	10 / 100	1096 ms	12704 KiB

island

#include <bits/stdc++.h>
using namespace std;
int main() {
	int N, M;
	cin >> N >> M;
	vector<int> vals(N);
	for(int i = 0; i < N; i++)
		cin >> vals[i];
	vector<vector<int>> roads(N, vector<int>());
	for(int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		roads[a].push_back(b);
		roads[b].push_back(a);
	}
	for(int i = 0; i < N; i++) {
		vector<bool> visited(N, false);
		visited[i] = true;
		long long current = vals[i];
		priority_queue<pair<int, int>> q;
		for(int a : roads[i]) {
			q.push(make_pair(-vals[a], a));
			visited[a] = true;
		}
		bool bb = true;
		while(!q.empty()) {
			int cost, vertex;
			tie(cost, vertex) = q.top();
			cost = -cost;
			q.pop();
			if(cost > current) {
				bb = false;
				break;
			}
			current += cost;
			for(int a : roads[vertex]) {
				if(visited[a]) continue;
				q.push(make_pair(-vals[a], a));
				visited[a] = true;
			}
		}
		cout << bb;
	}
	return 0;
}

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