제출 #697989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697989		Duy_e	Stranded Far From Home (BOI22_island)	C++14	10 / 100	483 ms	85624 KiB

island

#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 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35