Submission #722898

#	Time	Username	Problem	Language	Result	Execution time	Memory
722898		MurotY	Stranded Far From Home (BOI22_island)	C++14	0 / 100	312 ms	35928 KiB

island

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz size()
using namespace std;
const double pi = 2 * acos(0.0);
const ll N=1e6+7, M=998244353;
vector <pair <ll,ll>> g[N];
ll a[N];

void solve()
{
	int n, m;
	cin >> n >> m;
	
	for (int i=1;i<=n;i++) cin >> a[i];
	for (int i=1;i<=m;i++){
		int x, y;
		cin >> x >> y;
		g[x].push_back({a[y], y});
		g[y].push_back({a[x], x});
	}
	for (int i=1;i<=n;i++) sort(all(g[i]));
    if (n <= 2000 && m <= 2000){
		for (int i=1;i<=n;i++){
			priority_queue <ll, vector <ll>, greater <ll>> q;
			vector <bool> u(n+5, 0);
			q.push(i);
			ll sum=a[i], cnt=0;
			while (!q.empty()){
			     ll x=q.top();
			     q.pop();
			     if (u[x]) continue;
				u[x]=1; cnt++;
				for (auto l:g[x]){
					if (sum >= l.ff) {
						sum+=l.ff;
						q.push(l.ss);
					}
				}
			}
			if (cnt == n) cout << "1 ";
			else cout << "0 ";
		}		
	}
	return ;
}
int main(){
//	ios;
	int t=1;	
//	cin >> t;
	while (t--){ 
	    solve();
	    cout << "\n";
	}
	return 0;
}

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