Submission #1121591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121591		vjudge1	Stranded Far From Home (BOI22_island)	C++17	100 / 100	390 ms	95360 KiB

island

#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
#define int long long

typedef long long ll;
using namespace std;
const int maxn = 1e6 + 12;
const int mod = 1e9 + 7;

vector<int> g[maxn], e[maxn];
int ans[maxn], s[maxn];
bool used[maxn];
set<int> st;
int a[maxn], p[maxn];
int n, m, k;

int get(int x) {
    if(p[x] == x) return x;
    return p[x] = get(p[x]);
}

void merge(int a, int b) {
    a = get(a), b = get(b);
    if(a == b) {
        return;
    }
    if(e[a].size() > e[b].size()) {
        swap(a, b);
    }
    p[a] = b;
    s[b] += s[a];
    for(int x : e[a]) {
        e[b].push_back(x);
    }
}

void solve() {
    cin >> n >> m;
    vector<int> q(n);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = i;
        s[i] = a[i];
        e[i] = {i};
        q[i - 1] = i;
        st.insert(i);
    }
    vector<pair<int, int>> ord;
    while(m--) {
        int a, b;
        cin >> a >> b;
        ord.push_back({a, b});
        g[a].push_back(b);
        g[b].push_back(a);
    }
    sort(q.begin(), q.end(), [](int i, int j) {
        return a[i] < a[j];
    });
    for(int v : q) {
        used[v] = 1;
        for(int to : g[v]) {
            if(!used[to]) continue;
            to = get(to);
            if(get(v) == get(to)) {
                continue;
            }
            if(s[to] < a[v]) {
                for(int x : e[to]) {
                    st.erase(x);
                }
                e[to].clear();
            }
            merge(v, to);
        }
    }
    for(int x : st) {
        ans[x] = 1;
    }
    for(int i = 1; i <= n; i++) {
        cout << ans[i];
    }
    cout << ent;
}

signed main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;

//    cin >> t;
    while(t--){
        solve();
    }
}

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