Submission #711106

#	Time	Username	Problem	Language	Result	Execution time	Memory
711106		WH8	Stranded Far From Home (BOI22_island)	C++14	10 / 100	1087 ms	19924 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lll pair<int, pair<int, int>>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);

int p[200005];
int gz[200005];

vector<int> bfs[200005];

int par(int x){
	if (p[x] == x) return x;
	return p[x] = par(p[x]);
}

void merge(int a, int b){
	int x = par(a), y = par(b);
	if (x == y) return;
	if (gz[x] < gz[y]){
		p[x] = y;
	}
	else {
		p[y] = x;
	}
}

int32_t main(){
	FASTIO
	int n, m; cin >> n >> m;
	vector<vi> al(n+1);
	vector<int> v(n); iloop(0, n) {
		int c;
		cin >> c;
		v[i] = c;
	}
	iloop(0, m){
		int a, b; cin >> a >> b;
		a--; b--;
		al[a].pb(b); al[b].pb(a);
	}
	bool ans[n]; iloop(0, n) ans[i] = 0;
	iloop(0, n){
		//cout << endl << i << endl;
		priority_queue<pll, vector<pll>, greater<pll>> pq;
		bool vis[n];
		bool fail = 0;
		iloop(0, n) vis[i] = 0;
		vis[i] = true;
		pq.emplace(0, i);
		int p = v[i];
		while (!pq.empty()){
			int gain = pq.top().f, cur = pq.top().s; pq.pop();
			//debug(cur);
			if (gain > p) {
				fail = 1;
				break;
			}
			p += gain;
			for (auto it : al[cur]){
				if (vis[it]) continue;
				vis[it] = true;
				pq.emplace(v[it], it);
			}
		}
		if (fail){
			ans[i] = 0;
		}
		else ans[i] = 1;
	}
	iloop(0, n) cout << ans[i];
}

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