Submission #1188430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188430		qwusha	Stranded Far From Home (BOI22_island)	C++20	10 / 100	1093 ms	18968 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#define int long long


vector<vector<int>> g;

signed main() {
    int n, m;
    cin >> n >> m;
    vector<int> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    g.resize(n);
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        g[v - 1].push_back(u - 1);
        g[u - 1].push_back(v - 1);
    }
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        vector<int> used(n);
        int cursz = s[i];
        used[i] = 1;
        set<pair<int, int>> st;
        for (auto u : g[i]) {
            st.insert({s[u], u});
        }
        while (!st.empty()) {
            auto pa = *st.begin();
            int siz = pa.fi;
            int v = pa.se;
            st.erase(pa);
            if (used[v])
                continue;
            if (siz <= cursz) {
                cursz += siz;
                used[v] = 1;
                for (auto u : g[v]) {
                    if (!used[u]) {
                        st.insert({s[u], u});
                    }
                }
            }
        }
        bool ok = 1;
        for (int j = 0; j < n; j++) {
            if (!used[j])
                ok = 0;
        }
        ans[i] = ok;
        cout << ans[i];
    }
}

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