oj.uz

Submission #697970

# Submission time Handle Problem Language Result Execution time Memory
697970 2023-02-11T16:30:10 Z Duy_e Stranded Far From Home (BOI22_island) C++14
0 / 100
 517 ms 126832 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], 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;
            st[i].insert(pii(s[i], 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;
        if (st[u].size() > st[v].size()) swap(u, v);
        st[v].insert(st[u].begin(), st[u].end());
        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 u;
    }
}

int 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;

    rep(i, 1, n) {
        int u = a[i].nd;
        for (int v: d[u]) {
            DSU_set_merge :: uni(u, v);
            if (s[v] <= s[u] && pos[v] < pos[u])
                DSU :: uni(u, v);
        }
        f[u] = DSU :: sz[DSU :: find(u)];
        nxt[u] = DSU_set_merge :: find_greater(u, a[i]);
    }

    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];
    }

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

    return 0;
}

Subtask #1
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 Correct 7 ms 14364 KB Output is correct
4 Incorrect 9 ms 14952 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14428 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Runtime error 137 ms 85328 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 8 ms 14420 KB Output is correct
2 Incorrect 491 ms 126832 KB Output isn't correct
3 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 Incorrect 517 ms 88536 KB Output isn't correct
3 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 7 ms 14420 KB Output is correct
3 Correct 7 ms 14364 KB Output is correct
4 Incorrect 9 ms 14952 KB Output isn't correct
5 Halted 0 ms 0 KB -