제출 #1097417

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097417		HaciyevAlik	Stranded Far From Home (BOI22_island)	C++14	10 / 100	304 ms	632 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define oo 100000000000000000
const int mx = 2005;

int s[mx];
vector<int> g[mx];

signed main() {
    ios::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];
    }
    for(int i = 1; i <= m; ++i) {
        int u,v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= n; ++i) {
        priority_queue<pair<int,int>> pq;
        vector<bool> used(n + 1, 0);
        used[i] = true;
        int val = s[i];
        for(int v : g[i]) {
            pq.push({-s[v], v});
        }
        while(!pq.empty() && -pq.top().first <= val) {
            int v = pq.top().second;
            used[v] = 1;
            val += (-pq.top().first);
            pq.pop();   
            for(int go : g[v]) {
                if(!used[go]) {
                    pq.push({-s[go], go});
                }
            }
        }
        int cnt = 0;
        for(int j = 1; j <= n; ++j) {
            cnt += used[j];
        }
        if(cnt == n) {
            cout << "1";
        } else {
            cout << "0";
        }
    }
    return 0;
}

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