oj.uz

Submission #859065

# Submission time Handle Problem Language Result Execution time Memory
859065 2023-10-09T15:51:29 Z vgtcross Stranded Far From Home (BOI22_island) C++17
10 / 100
 131 ms 38104 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) {
        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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Incorrect 4 ms 19036 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 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 98 ms 35928 KB Output is correct
4 Correct 97 ms 32336 KB Output is correct
5 Correct 131 ms 33116 KB Output is correct
6 Correct 118 ms 33356 KB Output is correct
7 Correct 121 ms 33364 KB Output is correct
8 Correct 105 ms 33540 KB Output is correct
9 Correct 91 ms 33348 KB Output is correct
10 Correct 86 ms 37128 KB Output is correct
11 Correct 77 ms 37116 KB Output is correct
12 Correct 114 ms 32084 KB Output is correct
13 Correct 91 ms 32084 KB Output is correct
14 Correct 84 ms 32252 KB Output is correct
15 Correct 93 ms 38104 KB Output is correct
16 Correct 75 ms 37216 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 109 ms 33364 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 119 ms 33620 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 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Incorrect 4 ms 19036 KB Output isn't correct
5 Halted 0 ms 0 KB -