Submission #1305671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305671		tab	Stranded Far From Home (BOI22_island)	C++20	100 / 100	206 ms	57392 KiB

island

#include "bits/stdc++.h"
using namespace std;
#define intt long long
#define fi first
#define se second

const intt mxN = 2e5+1;
const intt LG = 20;
const intt inf = 1e18; 
const intt lll = 1232132; 
intt dx[4] = {1, -1, 0ll, 0ll};
intt dy[4] = {0, 0, 1, -1};

intt n, m;
vector<intt> a(mxN), sum(mxN), ans(mxN), var(mxN);
vector<vector<intt>> graph, comp;

struct DSU {
    vector<intt> parent, sze;
    DSU(intt n) {
        parent.resize(n+1);
        sze.resize(n+1);
        for(intt i = 1; i <= n; i++) {
            // cout << "ZRO" << endl;
            parent[i] = i;
            sze[i] = 1;
            comp[i].push_back(i);
            sum[i] = a[i];
        }
    }

    intt root(intt x) {
        if(parent[x] == x) return parent[x];
        else return parent[x] = root(parent[x]);
    }

    void unite(intt a, intt b) {
        a = root(a);
        b = root(b);
        if(a == b) return;
        if(sze[a] < sze[b]) swap(a, b);
        sze[a] += sze[b];
        sum[a] += sum[b];
        parent[b] = a;
        for(auto u : comp[b]) comp[a].push_back(u);
        comp[b].clear();
    }
};

bool cmp(intt &A, intt &b) {
    return a[A] < a[b]; 
}

void smile() {
    cin >> n >> m;
    a.resize(n + 1);
    graph.assign(n + 15, vector<intt> {});
    comp.assign(n + 15, vector<intt> {});
    for(intt i = 1; i <= n; i++) {
        ans[i] = 1;
        cin >> a[i];
    }

    for(intt i = 1; i <= m; i++) { 
        intt a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<intt> v;
    for(intt i = 0; i < n; i++) v.push_back(i + 1);
    sort(v.begin(), v.end(), cmp);
    var[v[0]] = 1;
    DSU dsu(n + 5);
    for(intt i = 0; i < n; i++) {
        intt node = v[i];
        for(auto u : graph[node]) {
            if(dsu.root(u) == dsu.root(node) || a[u] > a[node]) continue;
            if(a[node] > sum[dsu.root(u)]) {
                for(auto nod : comp[dsu.root(u)]) {
                    ans[nod] = 0ll;
                }
            }
            dsu.unite(u, node);
        }
    }
    for(intt i = 1; i <= n; i++) {
        cout << ans[i];
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);

    // freopen("island.in", "r", stdin);
    // freopen("island.out", "w", stdout);

    intt t = 1, buu = 1;
    // cin >> t;
    while(t--){
        // cout << "Case #" << buu++ << ": ";
        smile();
    }
}

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