Submission #1109513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109513		Zero_OP	Stranded Far From Home (BOI22_island)	C++14	10 / 100	1088 ms	17172 KiB

island

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, M;
    cin >> N >> M;
    vector<int> a(N);
    for(int i = 0; i < N; ++i){
        cin >> a[i];
    }

    vector<vector<int>> adj(N);
    while(M--){
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<bool> vis(N);
    auto solve = [&](int s) -> bool{
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        fill(vis.begin(), vis.end(), false);

        long long have = a[s];
        vis[s] = true;
        for(int u : adj[s]){
            if(!vis[u]){
                vis[u] = true;
                pq.push({a[u], u});
            }
        }

        while(!pq.empty()){
            int demand, u;
            tie(demand, u) = pq.top(); pq.pop();
            if(demand > have) return false;
            have += demand;

            for(auto v : adj[u]){
                if(!vis[v]){
                    vis[v] = true;
                    pq.push({a[v], v});
                }
            }
        }

        return true;
    };

    for(int i = 0; i < N; ++i){
        cout << solve(i);
    }

    return 0;
}

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