Submission #578566

#	Time	Username	Problem	Language	Result	Execution time	Memory
578566		Jarif_Rahman	Stranded Far From Home (BOI22_island)	C++17	100 / 100	164 ms	26796 KiB

island

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

void merge_vector(vector<int> &a, vector<int> &b){
    if(b.size() > a.size()) swap(a, b);
    while(!b.empty()) a.pb(b.back()), b.pop_back();
}

struct rechability_tree{
    int n;
    vector<int> p;
    vector<ll> s, sum;
    vector<vector<int>> sth;
    rechability_tree(int _n){
        n = _n;
        p.assign(n, -1);
        s.assign(n, 0);
        sum.assign(n, 0);
        sth.assign(n, {});
        for(int i = 0; i < n; i++) p[i] = i;
        for(int i = 0; i < n; i++) sth[i].pb(i);
    }
    int get(int nd){
        if(p[nd] != nd) p[nd] = get(p[nd]);
        return p[nd];
    }
    void unite(int a, int b){
        if(get(a) == get(b)) return;
        a = get(a), b = get(b);
        if(sum[b] >= s[a]) merge_vector(sth[a], sth[b]);
        sum[a]+=sum[b];
        p[b] = a;
    }
};

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

    int n, m; cin >> n >> m;

    vector<ll> s(n);
    for(ll &x: s) cin >> x;

    rechability_tree rt(n);
    for(int i = 0; i < n; i++) rt.s[i] = s[i], rt.sum[i] = s[i];

    vector<pair<int, int>> edges;
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b; a--, b--;
        if(s[b] > s[a]) swap(a, b);
        edges.pb({a, b});
    }

    sort(edges.begin(), edges.end(), [&s](pair<int, int> A, pair<int, int> B){
        return make_pair(s[A.f], s[A.sc]) < make_pair(s[B.f], s[B.sc]);
    });

    for(auto [a, b]: edges) rt.unite(a, b);

    int p = rt.get(0);

    str ans(n, '0');
    for(int x: rt.sth[p]) ans[x] = '1';

    cout << ans << "\n";
}

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