Submission #599796

#	Time	Username	Problem	Language	Result	Execution time	Memory
599796		yanndev	Stranded Far From Home (BOI22_island)	C++17	100 / 100	374 ms	37808 KiB

island

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

const int MX_N = 2e5 + 42;

int par[MX_N];
int sum[MX_N];
int guys[MX_N];
bool isOk[MX_N];
vector<int> graph[MX_N];
vector<int> dsuTree[MX_N];

int find(int node) {
    if (par[node] < 0)
        return node;
    return par[node] = find(par[node]);
}

void unite(int u, int v) {
    //cout << "edge " << u + 1 << ' ' << v + 1 << '\n';
    u = find(u);
    v = find(v);
    if (u == v)
        return;
    //cout << " compo is " << u + 1 << '\n';
    if (sum[u] < guys[v]) {
        //cout << "nok\n";
        isOk[u] = false;
    }
    par[v] += par[u];
    par[u] = v;
    sum[v] += sum[u];
    dsuTree[v].push_back(u);
}

void upd(int node, bool fuck) {
    //cout << "ucr is " << node << '\n';
    fuck &= isOk[node];
    for (auto& x: dsuTree[node])
        upd(x, fuck);
    isOk[node] = fuck;
}

signed main() {
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> nodes {};

    for (int i = 0; i < n; i++) {
        cin >> guys[i];
        nodes.push_back({guys[i], i});
        par[i] = -1;
        sum[i] = guys[i];
        isOk[i] = true;
    }
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    sort(nodes.begin(), nodes.end());
    for (int i = 0; i < n; i++)
        for (auto& x: graph[nodes[i].se])
            if (make_pair(guys[x], x) < nodes[i])
                unite(x, nodes[i].se);
    
    upd(nodes.back().se, true);
    /*for (int i = 0; i < n; i++) {
        for (auto& x: dsuTree[i]) {
            cout << "dsu edge " << i + 1 << " to " << x + 1 << '\n';
        }
    }*/
    for (int i = 0; i < n; i++)
        cout << isOk[i];
    cout << '\n';
}

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