Submission #1041976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041976		Blagoj	Stranded Far From Home (BOI22_island)	C++17	100 / 100	102 ms	40396 KiB

island

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 2e5 + 100;

vector<ll> s(mxn), ldr(mxn), rnk(mxn), mx(mxn), p[mxn];

int Find(int x) {
    if (ldr[x] == x) return x;
    return ldr[x] = Find(ldr[x]);
}

void Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return;
    if (rnk[x] < mx[y]) p[x].clear();
    if (rnk[y] < mx[x]) p[y].clear();
    if (p[x].size() < p[y].size()) swap(x, y);
    for (auto el : p[y]) p[x].push_back(el);
    ldr[y] = x;
    rnk[x] += rnk[y];
    mx[x] = max(mx[x], mx[y]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i];
    vector<pair<int, int>> edg;
    for (int i = 0; i < m; i++) {
        int f, t;
        cin >> f >> t;
        edg.push_back({f, t});
    }
    sort(all(edg), [&] (pair<int, int> a, pair<int, int> b) {
        return max(s[a.first], s[a.second]) < max(s[b.first], s[b.second]);
    });
    for (int i = 1; i <= n; i++) {
        ldr[i] = i;
        rnk[i] = s[i];
        p[i] = {i};
        mx[i] = s[i];
    }
    for (auto x : edg) Union(x.first, x.second);
    bitset<mxn> ans;
    for (auto x : p[Find(1)]) ans[x] = 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