oj.uz

Submission #697989

# Submission time Handle Problem Language Result Execution time Memory
697989 2023-02-11T17:50:29 Z Duy_e Stranded Far From Home (BOI22_island) C++14
10 / 100
 483 ms 85624 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define st first
#define nd second
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;

const long long INF = 1e18;
const long long N = 2e5;
ll s[N], n, m, f[N], pos[N], ans[N];
pii a[N];
ll nxt[N];

vector <int> d[N];

namespace DSU {
    int par[N];
    ll sz[N];

    void init() {
        rep(i, 1, n) par[i] = i, sz[i] = s[i];
    }

    int find(int u) {
        return u == par[u] ? u : par[u] = find(par[u]);
    }

    void uni(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return;
        par[u] = v;
        sz[v] += sz[u];
    }
}

namespace DSU_set_merge {
    set <pii> st[N];
    int par[N];

    void init() {
        rep(i, 1, n) {
            par[i] = i;
            for (int v: d[i]) if (s[v] >= s[i])
                st[i].insert(pii(s[v], v));
        }
    }

    int find(int u) {
        return u == par[u] ? u : par[u] = find(par[u]);
    }

    void uni(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return;
        if (st[u].size() > st[v].size()) swap(u, v);
        st[v].insert(st[u].begin(), st[u].end());
        st[u].clear();
        par[u] = v;
    }

    int find_greater(int u, pii x) {
        int rt = find(u);
        auto it = st[rt].upper_bound(x);
        if (it != st[rt].end()) return it->nd;
        return 0;
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    rep(i, 1, n) {
        cin >> s[i];
        a[i] = {s[i], i};
    }


    rep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        d[u].push_back(v);
        d[v].push_back(u);
    }

    DSU :: init();
    DSU_set_merge :: init();

    sort(a + 1, a + 1 + n);
    rep(i, 1, n) pos[a[i].nd] = i;

    s[0] = 1e9;
    rep(i, 1, n) {
        int u = a[i].nd;
        nxt[u] = 0;
        for (int v: d[u]) {

            if (s[v] <= s[u]) {
                DSU_set_merge :: uni(u, v);
                int tmp = DSU_set_merge :: find_greater(v, a[i]);
                if (s[tmp] <= s[nxt[u]])
                    nxt[u] = tmp;
            } else {
                if (s[v] <= s[nxt[u]])
                    nxt[u] = v;
            }

            if (s[v] <= s[u] && pos[v] < pos[u])
                DSU :: uni(u, v);
        }

        if (nxt[u] == 0) nxt[u] = u;
        f[u] = DSU :: sz[DSU :: find(u)];
        //cout << a[i].st << ' ' << a[i].nd << ' ' << nxt[u] << ' ' << f[u] << '\n';
    }

    ans[a[n].nd] = true;
    rrep(i, n - 1, 1) {
        int u = a[i].nd;
        int v = nxt[u];
        ans[u] = f[u] >= s[v] && ans[v];
    }

    rep(i, 1, n) cout << ans[i];

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14472 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 9 ms 14676 KB Output is correct
5 Correct 9 ms 14804 KB Output is correct
6 Correct 10 ms 14804 KB Output is correct
7 Correct 9 ms 14676 KB Output is correct
8 Correct 9 ms 14668 KB Output is correct
9 Correct 9 ms 14804 KB Output is correct
10 Correct 9 ms 14808 KB Output is correct
11 Correct 9 ms 14676 KB Output is correct
12 Correct 10 ms 14696 KB Output is correct
13 Correct 10 ms 14888 KB Output is correct
14 Correct 11 ms 14804 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Runtime error 141 ms 82940 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14456 KB Output is correct
2 Correct 457 ms 47308 KB Output is correct
3 Runtime error 173 ms 82988 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 461 ms 48628 KB Output is correct
3 Correct 483 ms 48516 KB Output is correct
4 Runtime error 163 ms 85624 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14472 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 9 ms 14676 KB Output is correct
5 Correct 9 ms 14804 KB Output is correct
6 Correct 10 ms 14804 KB Output is correct
7 Correct 9 ms 14676 KB Output is correct
8 Correct 9 ms 14668 KB Output is correct
9 Correct 9 ms 14804 KB Output is correct
10 Correct 9 ms 14808 KB Output is correct
11 Correct 9 ms 14676 KB Output is correct
12 Correct 10 ms 14696 KB Output is correct
13 Correct 10 ms 14888 KB Output is correct
14 Correct 11 ms 14804 KB Output is correct
15 Correct 7 ms 14420 KB Output is correct
16 Correct 7 ms 14420 KB Output is correct
17 Runtime error 141 ms 82940 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -