oj.uz

Submission #697990

# Submission time Handle Problem Language Result Execution time Memory
697990 2023-02-11T17:52:05 Z Duy_e Stranded Far From Home (BOI22_island) C++14
100 / 100
 728 ms 65164 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 + 5;
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] = 2e9;
    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 8 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 9 ms 14752 KB Output is correct
5 Correct 9 ms 14804 KB Output is correct
6 Correct 10 ms 14852 KB Output is correct
7 Correct 9 ms 14728 KB Output is correct
8 Correct 9 ms 14676 KB Output is correct
9 Correct 9 ms 14804 KB Output is correct
10 Correct 10 ms 14744 KB Output is correct
11 Correct 9 ms 14804 KB Output is correct
12 Correct 9 ms 14788 KB Output is correct
13 Correct 9 ms 14804 KB Output is correct
14 Correct 10 ms 14808 KB Output is correct

Subtask #2
10.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 185 ms 47436 KB Output is correct
4 Correct 279 ms 62988 KB Output is correct
5 Correct 382 ms 49628 KB Output is correct
6 Correct 397 ms 50768 KB Output is correct
7 Correct 406 ms 50636 KB Output is correct
8 Correct 456 ms 63220 KB Output is correct
9 Correct 290 ms 50576 KB Output is correct
10 Correct 196 ms 51396 KB Output is correct
11 Correct 325 ms 63976 KB Output is correct
12 Correct 547 ms 61976 KB Output is correct
13 Correct 321 ms 62876 KB Output is correct
14 Correct 320 ms 63008 KB Output is correct
15 Correct 196 ms 50636 KB Output is correct
16 Correct 146 ms 50268 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 447 ms 47212 KB Output is correct
3 Correct 460 ms 47528 KB Output is correct
4 Correct 296 ms 63276 KB Output is correct
5 Correct 280 ms 63008 KB Output is correct
6 Correct 461 ms 51824 KB Output is correct
7 Correct 225 ms 51940 KB Output is correct
8 Correct 232 ms 51904 KB Output is correct
9 Correct 149 ms 50820 KB Output is correct
10 Correct 204 ms 51824 KB Output is correct
11 Correct 243 ms 52936 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 456 ms 48604 KB Output is correct
3 Correct 469 ms 48512 KB Output is correct
4 Correct 487 ms 48696 KB Output is correct
5 Correct 661 ms 63072 KB Output is correct
6 Correct 592 ms 61924 KB Output is correct
7 Correct 302 ms 63964 KB Output is correct
8 Correct 190 ms 56844 KB Output is correct
9 Correct 287 ms 43084 KB Output is correct
10 Correct 728 ms 63052 KB Output is correct
11 Correct 234 ms 53068 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 9 ms 14752 KB Output is correct
5 Correct 9 ms 14804 KB Output is correct
6 Correct 10 ms 14852 KB Output is correct
7 Correct 9 ms 14728 KB Output is correct
8 Correct 9 ms 14676 KB Output is correct
9 Correct 9 ms 14804 KB Output is correct
10 Correct 10 ms 14744 KB Output is correct
11 Correct 9 ms 14804 KB Output is correct
12 Correct 9 ms 14788 KB Output is correct
13 Correct 9 ms 14804 KB Output is correct
14 Correct 10 ms 14808 KB Output is correct
15 Correct 7 ms 14420 KB Output is correct
16 Correct 7 ms 14420 KB Output is correct
17 Correct 185 ms 47436 KB Output is correct
18 Correct 279 ms 62988 KB Output is correct
19 Correct 382 ms 49628 KB Output is correct
20 Correct 397 ms 50768 KB Output is correct
21 Correct 406 ms 50636 KB Output is correct
22 Correct 456 ms 63220 KB Output is correct
23 Correct 290 ms 50576 KB Output is correct
24 Correct 196 ms 51396 KB Output is correct
25 Correct 325 ms 63976 KB Output is correct
26 Correct 547 ms 61976 KB Output is correct
27 Correct 321 ms 62876 KB Output is correct
28 Correct 320 ms 63008 KB Output is correct
29 Correct 196 ms 50636 KB Output is correct
30 Correct 146 ms 50268 KB Output is correct
31 Correct 7 ms 14420 KB Output is correct
32 Correct 447 ms 47212 KB Output is correct
33 Correct 460 ms 47528 KB Output is correct
34 Correct 296 ms 63276 KB Output is correct
35 Correct 280 ms 63008 KB Output is correct
36 Correct 461 ms 51824 KB Output is correct
37 Correct 225 ms 51940 KB Output is correct
38 Correct 232 ms 51904 KB Output is correct
39 Correct 149 ms 50820 KB Output is correct
40 Correct 204 ms 51824 KB Output is correct
41 Correct 243 ms 52936 KB Output is correct
42 Correct 7 ms 14420 KB Output is correct
43 Correct 456 ms 48604 KB Output is correct
44 Correct 469 ms 48512 KB Output is correct
45 Correct 487 ms 48696 KB Output is correct
46 Correct 661 ms 63072 KB Output is correct
47 Correct 592 ms 61924 KB Output is correct
48 Correct 302 ms 63964 KB Output is correct
49 Correct 190 ms 56844 KB Output is correct
50 Correct 287 ms 43084 KB Output is correct
51 Correct 728 ms 63052 KB Output is correct
52 Correct 234 ms 53068 KB Output is correct
53 Correct 7 ms 14436 KB Output is correct
54 Correct 7 ms 14432 KB Output is correct
55 Correct 7 ms 14392 KB Output is correct
56 Correct 9 ms 14804 KB Output is correct
57 Correct 10 ms 14832 KB Output is correct
58 Correct 10 ms 14884 KB Output is correct
59 Correct 9 ms 14756 KB Output is correct
60 Correct 9 ms 14700 KB Output is correct
61 Correct 9 ms 14828 KB Output is correct
62 Correct 10 ms 14804 KB Output is correct
63 Correct 9 ms 14804 KB Output is correct
64 Correct 9 ms 14832 KB Output is correct
65 Correct 8 ms 14864 KB Output is correct
66 Correct 9 ms 14804 KB Output is correct
67 Correct 196 ms 52008 KB Output is correct
68 Correct 256 ms 63052 KB Output is correct
69 Correct 354 ms 50592 KB Output is correct
70 Correct 403 ms 51936 KB Output is correct
71 Correct 400 ms 51792 KB Output is correct
72 Correct 438 ms 64484 KB Output is correct
73 Correct 290 ms 51692 KB Output is correct
74 Correct 192 ms 51724 KB Output is correct
75 Correct 325 ms 64136 KB Output is correct
76 Correct 502 ms 61984 KB Output is correct
77 Correct 298 ms 62864 KB Output is correct
78 Correct 294 ms 63112 KB Output is correct
79 Correct 207 ms 52044 KB Output is correct
80 Correct 162 ms 50804 KB Output is correct
81 Correct 444 ms 51660 KB Output is correct
82 Correct 475 ms 51920 KB Output is correct
83 Correct 326 ms 64624 KB Output is correct
84 Correct 287 ms 62836 KB Output is correct
85 Correct 476 ms 51824 KB Output is correct
86 Correct 224 ms 51812 KB Output is correct
87 Correct 223 ms 51944 KB Output is correct
88 Correct 212 ms 51820 KB Output is correct
89 Correct 270 ms 52964 KB Output is correct
90 Correct 469 ms 53048 KB Output is correct
91 Correct 439 ms 52940 KB Output is correct
92 Correct 501 ms 53348 KB Output is correct
93 Correct 670 ms 64644 KB Output is correct
94 Correct 575 ms 63012 KB Output is correct
95 Correct 309 ms 65164 KB Output is correct
96 Correct 190 ms 56908 KB Output is correct
97 Correct 286 ms 43084 KB Output is correct
98 Correct 723 ms 62940 KB Output is correct
99 Correct 236 ms 53068 KB Output is correct
100 Correct 114 ms 31188 KB Output is correct
101 Correct 469 ms 51964 KB Output is correct
102 Correct 555 ms 59568 KB Output is correct
103 Correct 416 ms 48348 KB Output is correct
104 Correct 430 ms 51468 KB Output is correct