Submission #1174259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174259		madamadam3	Stranded Far From Home (BOI22_island)	C++20	10 / 100	1095 ms	15168 KiB

island

#include <bits/stdc++.h>

using namespace std;

/*
    SAPO 2025 TC4 Day 1 - Candidates
    copied from BOI 2022 - Island

    45/100 pt solution here
*/

int n, m; 
int max_pop = 0;
vector<vector<int>> adj;
vector<int> s;

bool check(int start) {
    bool can = true;

    int cur_pop = s[start];
    vector<bool> vis(n + 1, false);

    priority_queue<pair<int, int>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int pop = -pq.top().first, cur = pq.top().second;
        pq.pop();
        vis[cur] = true;

        if (pop > cur_pop) return false;
        cur_pop += pop;

        if (cur_pop >= max_pop) return true; // hack to get 35 pts from the final task (bad cases)

        for (int nei : adj[cur]) {
            if (vis[nei]) continue;
            pq.push({-s[nei], nei});
        }
    }

    return can;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    s.resize(n + 1); for (int i = 1; i <= n; i++) cin >> s[i], max_pop = max(max_pop, s[i]);
    adj.assign(n + 1, vector<int>());

    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++) {
        cout << check(i) ? "1" : "0";
    }

    return 0;
}

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