Submission #654355

#	Time	Username	Problem	Language	Result	Execution time	Memory
654355		AlperenT	Stranded Far From Home (BOI22_island)	C++17	100 / 100	234 ms	35640 KiB

island

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, m, cnt[N];

struct DSU{
    int par[N];
    long long sum[N];
    vector<int> nodes[N];

    DSU(){
        for(int i = 1; i < N; i++){
            par[i] = i;
            nodes[i] = {i};
        }
    }

    int setfind(int a){
        if(par[a] == a) return a;
        else return par[a] = setfind(par[a]);
    }

    void setunion(int a, int b){
        a = setfind(a), b = setfind(b);

        if(a != b){
            if(nodes[b].size() > nodes[a].size()) swap(a, b);

            par[b] = par[a];
            sum[a] += sum[b];

            for(auto x : nodes[b]) nodes[a].push_back(x);
            nodes[b].clear();
        }
    }
};

DSU dsu;

pair<int, int> arr[N];

vector<int> graph[N];

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

    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        cin >> cnt[i];

        arr[i] = {cnt[i], i};

        dsu.sum[i] = cnt[i];
    }

    sort(arr + 1, arr + n + 1);

    for(int i = 0; i < m; i++){
        int a, b;

        cin >> a >> b;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for(int i = 1; i <= n; i++){
        int v = arr[i].second;

        for(auto e : graph[v]){
            if(cnt[e] <= cnt[v] && dsu.setfind(v) != dsu.setfind(e)){
                if(dsu.sum[dsu.setfind(e)] < cnt[v]) dsu.nodes[dsu.setfind(e)].clear();

                dsu.setunion(v, e);
            }
        }
    }

    string ans(n, '0');

    for(auto x : dsu.nodes[dsu.setfind(arr[n].second)]) ans[x - 1] = '1';

    cout << ans;
}

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