Submission #1305537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305537		HasanV11010238	Stranded Far From Home (BOI22_island)	C++20	100 / 100	264 ms	38964 KiB

island

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
vector<vector<int>> v;
vector<ll> sbt;
int cur;
struct DSU{
    vector<int> p, ro;
    int cmp;
    DSU(int n){
        p.assign(n + 1, -1);
        ro.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) ro[i] = i;
        cmp = n;
    }
    int find(int x){
        if (p[x] < 0) return x;
        return p[x] = find(p[x]);
    }
    void merge(int a, int b){
        int ora = a, orb = b;
        a = find(a), b = find(b);
        if (a == b) return;
        cmp--;
        if (p[a] > p[b]) swap(a, b), swap(ora, orb);
        if (sbt[ro[a]] >= sbt[orb]){
            v[cur].push_back(ro[a]);
        }
        if (sbt[ro[b]] >= sbt[ora]){
            v[cur].push_back(ro[b]);
        }
        p[a] += p[b];
        p[b] = a;
        sbt[cur] = sbt[ro[a]] + sbt[ro[b]];
        ro[a] = cur;
        cur++;
    }
};
int n;
vector<int> ans;
void dfs(int x){
    if (x <= n) ans[x] = 1;
    for (auto el : v[x]){
        dfs(el);
    }
}
int main(){
    int m, a, b;
    cin>>n>>m;
    sbt.assign(2 * n + 1, 0);
    v.assign(2 * n, vector<int>());
    ans.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin>>sbt[i];
    vector<vector<ll>> edg;
    for (int i = 1; i <= m; i++){
        cin>>a>>b;
        edg.push_back({max(sbt[a], sbt[b]), a, b});
    }
    cur = n + 1;
    DSU ds(n);
    sort(edg.begin(), edg.end());
    for (auto el : edg){
        ds.merge(el[1], el[2]);
    }
    if (ds.cmp == 1){
        dfs(cur - 1);
    }
    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