Submission #1305510

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

island

#include "bits/stdc++.h"

#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;i>=(a);i--)
#define R0F(i,a)ROF(i,0,a)
#define REP(a)F0R(_,a)

using namespace std;

const int mxn=2e5+20;

vector<int>aj[mxn];
int s[mxn];

int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n,m;cin>>n>>m;
	F0R(i,n)cin>>s[i];
	REP(m){
		int a,b;cin>>a>>b;
		a--,b--;
		aj[a].push_back(b);
		aj[b].push_back(a);
	}
	F0R(i,n){
		priority_queue<array<int,2>>pq;
		vector<bool>vis(n);
		vis[i]=true;
		for(int v:aj[i])pq.push({-s[v],v});
		long long sm=s[i];
		while(not pq.empty()){
			auto tp=pq.top();
			pq.pop();
			if(sm<-tp[0])break;
			if(vis[tp[1]])continue;
			sm-=tp[0];
			vis[tp[1]]=true;
			for(int v:aj[tp[1]])if(not vis[v]){
				pq.push({-s[v],v});
			}
		}
		int loc=0;
		F0R(j,n)if(vis[j])loc++;
		cout<<(loc==n);
	}
	cout<<'\n';
}

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