oj.uz

Submission #859068

# Submission time Handle Problem Language Result Execution time Memory
859068 2023-10-09T16:03:26 Z vgtcross Stranded Far From Home (BOI22_island) C++17
10 / 100
 128 ms 33620 KB 
#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) {
        int bigger = -1;
        if (sum[a] < sb) {
            bad[node[a]] = 1;
            bigger = b;
        }
        if (sum[b] < sa) {
            bad[node[b]] = 1;
            bigger = a;
        }
        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]);
        if (bigger != -1) bad[w] |= bad[node[bigger]];
        node[a] = w;
        ++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 c) {
    c += bad[u];
    if (ch[u].empty()) ans[u] = c == 0;
    for (int v : ch[u]) {
        dfs(v, 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, 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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18936 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Incorrect 4 ms 18780 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 95 ms 31488 KB Output is correct
4 Correct 86 ms 29008 KB Output is correct
5 Correct 119 ms 28756 KB Output is correct
6 Correct 118 ms 29180 KB Output is correct
7 Correct 128 ms 29176 KB Output is correct
8 Correct 110 ms 29012 KB Output is correct
9 Correct 92 ms 28940 KB Output is correct
10 Correct 93 ms 33616 KB Output is correct
11 Correct 76 ms 33616 KB Output is correct
12 Correct 96 ms 29008 KB Output is correct
13 Correct 84 ms 29076 KB Output is correct
14 Correct 87 ms 29060 KB Output is correct
15 Correct 102 ms 33620 KB Output is correct
16 Correct 80 ms 33508 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Incorrect 116 ms 28920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Incorrect 117 ms 29268 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18936 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Incorrect 4 ms 18780 KB Output isn't correct
5 Halted 0 ms 0 KB -