oj.uz

Submission #769447

# Submission time Handle Problem Language Result Execution time Memory
769447 2023-06-29T15:05:36 Z borisAngelov Stranded Far From Home (BOI22_island) C++17
25 / 100
 1000 ms 61384 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int maxn = 200005;

int n, m;

long long people[maxn];

vector<int> g[maxn];

bool answer[maxn];

int parent[maxn];

vector<int> nodes_in_component[maxn];
long long sum_component[maxn];

int root(int x)
{
    if (x == parent[x])
    {
        return x;
    }

    return parent[x] = root(parent[x]);
}

void connect(int x, int y)
{
    x = root(x);
    y = root(y);

    if (nodes_in_component[x].size() < nodes_in_component[y].size())
    {
        swap(x, y);
    }

    sum_component[x] += sum_component[y];

    for (auto node : nodes_in_component[y])
    {
        nodes_in_component[x].push_back(node);
    }

    parent[y] = x;
}

bool is_connected(int x, int y)
{
    return root(x) == root(y);
}

pair<int, int> sorted_nodes[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
    {
        cin >> people[i];
        answer[i] = true;
        sorted_nodes[i] = make_pair(people[i], i);
    }

    for (int i = 1; i <= n; ++i)
    {
        sum_component[i] = people[i];
        nodes_in_component[i].push_back(i);
        parent[i] = i;
    }

    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    for (int i = 1; i <= n; ++i)
    {
        sort(g[i].begin(), g[i].end(), [&](int x, int y)
        {
            return people[x] <= people[y];
        });
    }

    sort(sorted_nodes + 1, sorted_nodes + n + 1);

    for (int i = 1; i <= n; ++i)
    {
        int node = sorted_nodes[i].second;

        for (auto next_node : g[node])
        {
            if (people[node] < people[next_node])
            {
                continue;
            }

            int big_node = root(next_node);

            if (sum_component[big_node] < people[node])
            {
                for (auto blanked_node : nodes_in_component[big_node])
                {
                    answer[blanked_node] = false;
                }
            }

            if (is_connected(node, big_node) == false)
            {
                connect(node, big_node);
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        cout << answer[i];
    }

    cout << endl;

    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 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 5 ms 9940 KB Output is correct
10 Correct 6 ms 9904 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 6 ms 10036 KB Output is correct
13 Correct 5 ms 9880 KB Output is correct
14 Correct 6 ms 9956 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 104 ms 29328 KB Output is correct
4 Correct 105 ms 32116 KB Output is correct
5 Correct 150 ms 36996 KB Output is correct
6 Correct 163 ms 37828 KB Output is correct
7 Correct 150 ms 38016 KB Output is correct
8 Correct 126 ms 33524 KB Output is correct
9 Correct 117 ms 43232 KB Output is correct
10 Correct 110 ms 33756 KB Output is correct
11 Runtime error 87 ms 61384 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 168 ms 35288 KB Output is correct
3 Correct 172 ms 35208 KB Output is correct
4 Correct 116 ms 33548 KB Output is correct
5 Correct 97 ms 32296 KB Output is correct
6 Correct 172 ms 39704 KB Output is correct
7 Correct 121 ms 33832 KB Output is correct
8 Correct 119 ms 33532 KB Output is correct
9 Correct 76 ms 32632 KB Output is correct
10 Correct 101 ms 32772 KB Output is correct
11 Correct 131 ms 33312 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 176 ms 30992 KB Output is correct
3 Correct 194 ms 36016 KB Output is correct
4 Correct 179 ms 37052 KB Output is correct
5 Correct 199 ms 36228 KB Output is correct
6 Correct 171 ms 33824 KB Output is correct
7 Execution timed out 1075 ms 33044 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 5 ms 9940 KB Output is correct
10 Correct 6 ms 9904 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 6 ms 10036 KB Output is correct
13 Correct 5 ms 9880 KB Output is correct
14 Correct 6 ms 9956 KB Output is correct
15 Correct 4 ms 9684 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Correct 104 ms 29328 KB Output is correct
18 Correct 105 ms 32116 KB Output is correct
19 Correct 150 ms 36996 KB Output is correct
20 Correct 163 ms 37828 KB Output is correct
21 Correct 150 ms 38016 KB Output is correct
22 Correct 126 ms 33524 KB Output is correct
23 Correct 117 ms 43232 KB Output is correct
24 Correct 110 ms 33756 KB Output is correct
25 Runtime error 87 ms 61384 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -