Submission #640260

#	Time	Username	Problem	Language	Result	Execution time	Memory
640260		kebine	Stranded Far From Home (BOI22_island)	C++17	10 / 100	188 ms	1748 KiB

island

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>

using namespace std;

const int N = 20002;
vector<int>adj[N];
bool vis[N];
ll s[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >> s[i];

    while(m--){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1; i <= n; i++){
        memset(vis, 0, sizeof(vis));
        priority_queue<pll, vector<pll>, greater<pll>>q; q.emplace(0, i);
        vis[i] = true;
        int cnt = 0;
        ll cur = s[i];

        while(!q.empty()){
            auto [v, u] = q.top(); q.pop();
            if(cur < v) break;
            cnt++;
            cur += v;

            for(auto &v: adj[u]){
                if(!vis[v]){
                    vis[v] = true;
                    q.emplace(s[v], v);
                }
            }
        }

        if(cnt == n) cout << 1;
        else cout << 0;
    }

    cout << '\n';

    return 0;
}

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