Submission #1239152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239152		quannnguyen2009	Stranded Far From Home (BOI22_island)	C++20	100 / 100	162 ms	57672 KiB

island

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 2e5+5, mod = 1e9+7, inf = 1e18;

int n, m;
int a[N];
ii b[N];
bool ans[N];
vector<int> adj[N];

struct DSU {
    int par[N], sz[N], sum[N];
    vector<int> lst[N];
    void init(int n) {
        iota(par, par+n+1, 0);
        fill(sz, sz+n+1, 1);
        for (int i=1; i<=n; i++) sum[i] = a[i];
        for (int i=1; i<=n; i++) lst[i].pb(i);
    }
    int find(int u) {
        if (par[u] == u) return u;
        return par[u] = find(par[u]);
    }
    bool join(int u, int v) {
        u = find(u); v = find(v);
        if(u == v) return 0;
        if(sz[u]<sz[v]) swap(u, v);
        par[v] = u; sz[u] += sz[v];
        sum[u] += sum[v];
        for (int it: lst[v]) lst[u].pb(it);
        return 1;
    }     
    int csz(int u) {return sz[find(u)];}
    bool check(int u, int v) {
        return find(u)==find(v);
    }
} DSU;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        b[i] = {a[i], i};
    }
    DSU.init(n);
    for (int i=1; i<=m; i++) {
        int u, v; cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for (int i=1; i<=n; i++) ans[i] = 1;
    sort(b+1, b+n+1);
    for (int i=1; i<=n; i++) {
        set<int> st;
        for (int v: adj[b[i].se]) {
            if (a[v]<b[i].fi || (a[v]==b[i].fi && b[i].se>v)) st.insert(DSU.find(v));
        }
        for (int it: st) {
            if (DSU.sum[it]<b[i].fi) {
                for (int it_: DSU.lst[it])  ans[it_] = 0;
            }
        }
        for (int it: st) DSU.join(b[i].se, it);
    }
    for (int i=1; 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