Submission #881668

#	Time	Username	Problem	Language	Result	Execution time	Memory
881668		teesla	Stranded Far From Home (BOI22_island)	C++14	10 / 100	1089 ms	20752 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> ii;

vector<vector<int>> adj;
vector<int> v;int n,m;

bool ok(int x){

    vector<int> vis(n+2,0);
    vis[x] = 1;

    int sum = v[x];

    priority_queue<ii, vector<ii>, greater<ii>> q;

    for(auto i: adj[x]){vis[i] = 1; q.push({v[i], i});}

    while(!q.empty()){
        int val = q.top().first, id = q.top().second;
        q.pop();

        if(sum < val) return 0;
        for(auto k: adj[id]){
            if(vis[k]) continue;
            q.push({v[k], k});
            vis[k] = 1;
        }
        sum += val;
    }

    return true;

}

signed main(){

     cin >> n >> m;
    v.resize(n+2); adj.resize(n+2);

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

    for(int i=0; i<m; i++){
        int a,b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for(int i=1; i<=n; i++){
        if(ok(i))cout << 1;
        else cout <<0;
    }

    cout << endl;

}

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