Submission #1228580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228580		SpyrosAliv	Stranded Far From Home (BOI22_island)	C++20	100 / 100	134 ms	50744 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MN = 2e5+5;
int n, m;
vector<vector<int>> conn(MN), tree(MN);
int val[MN], root, par[MN], sz[MN], rep[MN];
vector<int> subSum(MN, 0);
vector<bool> poss(MN);

int find(int u) {
    if (par[u] == u) return u;
    return par[u] = find(par[u]);
}

void merge(int u, int v) {
    if (find(u) == find(v)) return;
    v = find(v);
    tree[u].push_back(rep[v]);
    int nxtRep = u;
    u = find(u);
    if (sz[u] > sz[v]) swap(u, v);
    par[u] = v;
    sz[v] += sz[u];
    rep[u] = rep[v] = nxtRep;
}

void calc_subs(int node, int par = 0) {
    subSum[node] = val[node];
    for (auto next: tree[node]) {
        if (next == par) continue;
        calc_subs(next, node);
        subSum[node] += subSum[next];
    }
}

void get_ans(int node, int par = 0) {
    poss[node] = true;
    for (auto next: tree[node]) {
        if (par == next) continue;
        if (subSum[next] >= val[node]) {
            get_ans(next, node);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        par[i] = i;
        sz[i] = 1;
        rep[i] = i;
    }
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        conn[u].push_back(v);
        conn[v].push_back(u);
    }
    vector<pair<int, int>> vals;
    for (int i = 1; i <= n; i++) vals.push_back({val[i], i});
    sort(vals.begin(), vals.end());
    vector<bool> added(n+1, false);
    for (auto [foo, u]: vals) {
        for (auto nxt: conn[u]) {
            if (!added[nxt]) continue;
            merge(u, nxt);
        }
        added[u] = true;
    }
    root = vals.back().second;
    calc_subs(root);
    get_ans(root);
    for (int i = 1; i <= n; i++) {
        if (poss[i]) {
            cout << 1;
        }
        else cout << 0;
    }
    cout << "\n";
}

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