Submission #1078888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078888		wangziyanmo	Stranded Far From Home (BOI22_island)	C++17	100 / 100	247 ms	31804 KiB

island

#include <bits/stdc++.h>
using namespace std;

#define int long long

pair<int,int> s[200010];
int v[200010];
vector<int> e[200010];
int vis[200010],ans[200010];

struct comp{
	int val,num;
	bool operator < (const comp &cmp) const{
		return val>cmp.val;
	}
};

signed main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,m;cin>>n>>m;
	for (int i=1;i<=n;i++){
		cin>>s[i].first;s[i].second=i;
		v[i]=s[i].first;
		ans[i]=-1;
	}
	sort(s+1,s+n+1);
	for (int i=1;i<=m;i++){
		int a,b;cin>>a>>b;
		e[a].push_back(b);e[b].push_back(a);
	}
	for (int i=1;i<=n;i++){
		if (ans[s[i].second]>=0) continue;
		priority_queue<comp> pq;
		int sum=0,mx=0;
		pq.push({s[i].first,s[i].second});
		vector<int> as;
		int got=1;
		vis[s[i].second]=i;
		while (pq.size()){
			auto k=pq.top();pq.pop();
			if (k.val>sum && sum>0){
				got=0;break;
			}
			if (k.val>=mx){
				if (ans[k.num]!=-1){
					got=ans[k.num];break;
				}
				mx=k.val;as.push_back(k.num);
			}
			sum+=k.val;
			for (auto x:e[k.num]){
				if (vis[x]==i) continue;
				vis[x]=i;
				pq.push({v[x],x});
			}
		}
		for (auto x:as) ans[x]=got;
	}
	for (int i=1;i<=n;i++) cout<<ans[i];
	cout<<"\n";
}

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