Submission #859065

#	Time	Username	Problem	Language	Result	Execution time	Memory
859065		vgtcross	Stranded Far From Home (BOI22_island)	C++17	10 / 100	131 ms	38104 KiB

island

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = 400400;

int dsu[N], sz[N];
int s[N];
vector<int> ch[N];
ll sum[N];
int node[N];
int w;
bool bad[N];
int ans[N];

void init(int n) {
    for (int i = 1; i <= n; ++i) {
        dsu[i] = i;
        sz[i] = 1;
        sum[i] = s[i];
        node[i] = i;
    }
}

int fs(int i) {
    if (dsu[i] == i) return i;
    return dsu[i] = fs(dsu[i]);
}

void us(int a, int b) {
    int sa = s[a];
    int sb = s[b];
    a = fs(a);
    b = fs(b);
    if (a != b) {
        if (sum[a] < sb) bad[node[a]] = 1;
        if (sum[b] < sa) bad[node[b]] = 1;
        if (sz[a] < sz[b]) swap(a, b);
        dsu[b] = a;
        sz[a] += sz[b];
        sum[a] += sum[b];
        ch[w].push_back(node[a]);
        ch[w].push_back(node[b]);
        node[a] = w++;
    }
}

bool cmp(pii a, pii b) {
    return make_pair(s[a.first], s[a.second]) < make_pair(s[b.first], s[b.second]);
}

void dfs(int u, int p, int c) {
    c += bad[u];
    if (ch[u].empty()) ans[u] = c == 0;
    for (int v : ch[u]) {
        dfs(v, u, c);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    w = n+1;
    
    for (int i = 1; i <= n; ++i) cin >> s[i];
    
    vector<pii> e(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        if (s[u] > s[v]) swap(u, v);
        e[i] = {u, v};
    }
    
    sort(e.begin(), e.end(), cmp);
    init(n);
    for (pii p : e) us(p.first, p.second);
    
    dfs(w-1, -1, 0);
    for (int i = 1; i <= n; ++i) cout << ans[i];
    cout << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    solve();
}

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