Submission #1188463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188463		qwusha	Stranded Far From Home (BOI22_island)	C++20	100 / 100	223 ms	41056 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;


int n;
vector<int> s;
vector<int> bad;

int nextval;


struct dsu {
    vector<int> sz, par, sum, prev;

    void init() {
        sz.resize(n);
        par.resize(n);
        sum.resize(n);
        for (int i = 0; i < n; i++) {
            sz[i] = 1;
            par[i] = i;
            sum[i] = s[i];
        }
    }
    int get_par(int v) {
        if (par[v] == v)
            return v;
        int ans = get_par(par[v]);
        par[v] = ans;
        return ans;
    }
    void merg(int v, int u) {
        v = get_par(v);
        u = get_par(u);
        if (v == u)
            return;
        sz[v] += sz[u];
        if (sum[u] < nextval) {
            bad.push_back(u);
        }
        if (sum[v] < nextval) {
            bad.push_back(v);
        }
        sum[v] += sum[u];
        par[u] = v;
    }
};


signed main() {
    int m;
    cin >> n >> m;
    s.resize(n);
    vector<pair<int, int>> a;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        a.push_back({s[i], i});
    }
    sort(a.begin(), a.end());
    g.resize(n);
    vector<vector<int>> edg(n);
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        if (s[v - 1] < s[u - 1])
            swap(v, u);
        edg[v - 1].push_back(u - 1);
        g[v - 1].push_back(u - 1);
        g[u - 1].push_back(v - 1);
    }
    dsu dsu;
    dsu.init();
    for (int i = 0; i < n; i++) {
        int v = a[i].se;
        nextval = s[v];
        for (auto u : edg[v]) {
            dsu.merg(v, u);
        }
    }
    reverse(bad.begin(), bad.end());
    vector<int> ans(n, 1);
    set<pair<int, int>> st;
    for (auto i : bad) {
        if (ans[i] == 0)
            continue;
        int cursz = s[i];
        ans[i] = 0;
        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 (ans[v] == 0)
                continue;
            if (siz <= cursz) {
                cursz += siz;
                ans[v] = 0;
                for (auto u : g[v]) {
                    if (ans[u] == 1) {
                        st.insert({s[u], u});
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i];
    }
}

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