Submission #847345

#	Time	Username	Problem	Language	Result	Execution time	Memory
847345		ArashJafariyan	Stranded Far From Home (BOI22_island)	C++17	0 / 100	173 ms	30988 KiB

island

#include <bits/stdc++.h>
using ll = long long;

#define pb push_back

const int N = 2e5 + 4;

int n, m, st[N], a[N], b[N], idx[N], par[N];
ll sum[N];
char ans[N];
std::vector<int> vset[N];

bool cmp(int i, int j) {
    int x = std::max(st[a[i]], st[b[i]]);
    int y = std::max(st[a[j]], st[b[j]]);
    return x < y;
}

int gr(int v) {
    std::stack<int> s;
    s.push(v);
    while (par[s.top()] != s.top()) {
        s.push(par[s.top()]);
    }

    int ret = s.top();
    while (!s.empty()) {
        par[s.top()] = ret;
        s.pop();
    }
    return ret;
}

void mrg(int v, int u, int w) {
    v = gr(v);
    u = gr(u);
    if (v == u) {
        return;
    }
    if (sum[v] > sum[u]) {
        std::swap(v, u);
    }

    bool b = sum[v] < w;
    for (int x : vset[v]) {
        vset[u].pb(v);
        if (b) {
            ans[x] = '0';
        }
    }
    sum[u] += sum[v];
    par[v] = u;
    return;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        std::cin >> sum[i];
        st[i] = sum[i];
        vset[i].pb(i);
        ans[i] = '1';
        par[i] = i;
    }
    for (int i = 0; i < m; ++i) {
        std::cin >> a[i] >> b[i];
        --a[i], --b[i];
        idx[i] = i;
    }
    std::sort(idx, idx + m, cmp); 
    
    for (int i = 0; i < m; ++i) {
        int j = idx[i];
        int w = std::max(st[a[j]], st[b[j]]);
        mrg(a[j], b[j], w);
    }
    for (int i = 0; i < n; ++i) {
        std::cout << ans[i];
    }
    return 0;
}

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