oj.uz

Submission #601044

# Submission time Handle Problem Language Result Execution time Memory
601044 2022-07-21T10:28:31 Z alextodoran Stranded Far From Home (BOI22_island) C++17
100 / 100
 230 ms 35588 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

int N, M;
int weight[N_MAX + 2];
vector <int> adj[N_MAX + 2];

int order[N_MAX + 2];

int root[N_MAX + 2];
ll sum[N_MAX + 2];

int findRoot (int u) {
    return (root[u] == 0 ? u : root[u] = findRoot(root[u]));
}

bool seen[N_MAX + 2];

vector <int> sons[N_MAX + 2];

bool answer[N_MAX + 2];
void dfs (int u, int parent = 0) {
    answer[u] = true;
    for (int v : sons[u]) {
        if (v != parent) {
            dfs(v, u);
        }
    }
}

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

    cin >> N >> M;
    for (int u = 1; u <= N; u++) {
        cin >> weight[u];
    }
    for (int i = 1; i <= M; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    iota(order + 1, order + N + 1, 1);
    sort(order + 1, order + N + 1, [&] (const int &u, const int &v) {
        return weight[u] < weight[v];
    });

    copy(weight + 1, weight + N + 1, sum + 1);

    for (int i = 1; i <= N; i++) {
        int u = order[i];
        seen[u] = true;
        for (int v : adj[u]) {
            if (seen[v] == true) {
                v = findRoot(v);
                if (v != u) {
                    if (sum[v] >= weight[u]) {
                        sons[u].push_back(v);
                    }
                    root[v] = u;
                    sum[u] += sum[v];
                }
            }
        }
    }
    dfs(order[N]);
    for (int u = 1; u <= N; u++) {
        cout << answer[u];
    }
    cout << "\n";

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 7 ms 9776 KB Output is correct
6 Correct 6 ms 9876 KB Output is correct
7 Correct 7 ms 9812 KB Output is correct
8 Correct 6 ms 9836 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9680 KB Output is correct
3 Correct 135 ms 25784 KB Output is correct
4 Correct 144 ms 27424 KB Output is correct
5 Correct 167 ms 24268 KB Output is correct
6 Correct 151 ms 25020 KB Output is correct
7 Correct 171 ms 25828 KB Output is correct
8 Correct 180 ms 27644 KB Output is correct
9 Correct 133 ms 24076 KB Output is correct
10 Correct 103 ms 24068 KB Output is correct
11 Correct 99 ms 25220 KB Output is correct
12 Correct 152 ms 26052 KB Output is correct
13 Correct 144 ms 27328 KB Output is correct
14 Correct 137 ms 28380 KB Output is correct
15 Correct 145 ms 34892 KB Output is correct
16 Correct 95 ms 33708 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 173 ms 22740 KB Output is correct
3 Correct 188 ms 25420 KB Output is correct
4 Correct 146 ms 30488 KB Output is correct
5 Correct 135 ms 28760 KB Output is correct
6 Correct 211 ms 26188 KB Output is correct
7 Correct 156 ms 34588 KB Output is correct
8 Correct 176 ms 34488 KB Output is correct
9 Correct 101 ms 33496 KB Output is correct
10 Correct 136 ms 25128 KB Output is correct
11 Correct 151 ms 26444 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 211 ms 23476 KB Output is correct
3 Correct 178 ms 27552 KB Output is correct
4 Correct 230 ms 25048 KB Output is correct
5 Correct 177 ms 28952 KB Output is correct
6 Correct 166 ms 27728 KB Output is correct
7 Correct 114 ms 25152 KB Output is correct
8 Correct 109 ms 32012 KB Output is correct
9 Correct 118 ms 19992 KB Output is correct
10 Correct 147 ms 25676 KB Output is correct
11 Correct 180 ms 24908 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 7 ms 9776 KB Output is correct
6 Correct 6 ms 9876 KB Output is correct
7 Correct 7 ms 9812 KB Output is correct
8 Correct 6 ms 9836 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9680 KB Output is correct
17 Correct 135 ms 25784 KB Output is correct
18 Correct 144 ms 27424 KB Output is correct
19 Correct 167 ms 24268 KB Output is correct
20 Correct 151 ms 25020 KB Output is correct
21 Correct 171 ms 25828 KB Output is correct
22 Correct 180 ms 27644 KB Output is correct
23 Correct 133 ms 24076 KB Output is correct
24 Correct 103 ms 24068 KB Output is correct
25 Correct 99 ms 25220 KB Output is correct
26 Correct 152 ms 26052 KB Output is correct
27 Correct 144 ms 27328 KB Output is correct
28 Correct 137 ms 28380 KB Output is correct
29 Correct 145 ms 34892 KB Output is correct
30 Correct 95 ms 33708 KB Output is correct
31 Correct 6 ms 9684 KB Output is correct
32 Correct 173 ms 22740 KB Output is correct
33 Correct 188 ms 25420 KB Output is correct
34 Correct 146 ms 30488 KB Output is correct
35 Correct 135 ms 28760 KB Output is correct
36 Correct 211 ms 26188 KB Output is correct
37 Correct 156 ms 34588 KB Output is correct
38 Correct 176 ms 34488 KB Output is correct
39 Correct 101 ms 33496 KB Output is correct
40 Correct 136 ms 25128 KB Output is correct
41 Correct 151 ms 26444 KB Output is correct
42 Correct 5 ms 9684 KB Output is correct
43 Correct 211 ms 23476 KB Output is correct
44 Correct 178 ms 27552 KB Output is correct
45 Correct 230 ms 25048 KB Output is correct
46 Correct 177 ms 28952 KB Output is correct
47 Correct 166 ms 27728 KB Output is correct
48 Correct 114 ms 25152 KB Output is correct
49 Correct 109 ms 32012 KB Output is correct
50 Correct 118 ms 19992 KB Output is correct
51 Correct 147 ms 25676 KB Output is correct
52 Correct 180 ms 24908 KB Output is correct
53 Correct 5 ms 9732 KB Output is correct
54 Correct 4 ms 9684 KB Output is correct
55 Correct 5 ms 9684 KB Output is correct
56 Correct 6 ms 9812 KB Output is correct
57 Correct 8 ms 9872 KB Output is correct
58 Correct 6 ms 9812 KB Output is correct
59 Correct 7 ms 9876 KB Output is correct
60 Correct 8 ms 9876 KB Output is correct
61 Correct 6 ms 9940 KB Output is correct
62 Correct 7 ms 9880 KB Output is correct
63 Correct 9 ms 9812 KB Output is correct
64 Correct 6 ms 9752 KB Output is correct
65 Correct 7 ms 9812 KB Output is correct
66 Correct 7 ms 9812 KB Output is correct
67 Correct 137 ms 28560 KB Output is correct
68 Correct 141 ms 27788 KB Output is correct
69 Correct 164 ms 23712 KB Output is correct
70 Correct 155 ms 25212 KB Output is correct
71 Correct 159 ms 24568 KB Output is correct
72 Correct 187 ms 27232 KB Output is correct
73 Correct 168 ms 24140 KB Output is correct
74 Correct 88 ms 22232 KB Output is correct
75 Correct 108 ms 23860 KB Output is correct
76 Correct 152 ms 25520 KB Output is correct
77 Correct 133 ms 27340 KB Output is correct
78 Correct 168 ms 27340 KB Output is correct
79 Correct 144 ms 33672 KB Output is correct
80 Correct 96 ms 34428 KB Output is correct
81 Correct 183 ms 25132 KB Output is correct
82 Correct 176 ms 25872 KB Output is correct
83 Correct 132 ms 26308 KB Output is correct
84 Correct 142 ms 28456 KB Output is correct
85 Correct 173 ms 27212 KB Output is correct
86 Correct 158 ms 35588 KB Output is correct
87 Correct 173 ms 35508 KB Output is correct
88 Correct 142 ms 24356 KB Output is correct
89 Correct 153 ms 23700 KB Output is correct
90 Correct 181 ms 25936 KB Output is correct
91 Correct 202 ms 27748 KB Output is correct
92 Correct 177 ms 27928 KB Output is correct
93 Correct 192 ms 28084 KB Output is correct
94 Correct 178 ms 27652 KB Output is correct
95 Correct 112 ms 27084 KB Output is correct
96 Correct 110 ms 31472 KB Output is correct
97 Correct 122 ms 20412 KB Output is correct
98 Correct 165 ms 27208 KB Output is correct
99 Correct 145 ms 26384 KB Output is correct
100 Correct 50 ms 13924 KB Output is correct
101 Correct 195 ms 27392 KB Output is correct
102 Correct 160 ms 25680 KB Output is correct
103 Correct 173 ms 22604 KB Output is correct
104 Correct 188 ms 23844 KB Output is correct