oj.uz

Submission #769449

# Submission time Handle Problem Language Result Execution time Memory
769449 2023-06-29T15:07:28 Z borisAngelov Stranded Far From Home (BOI22_island) C++17
25 / 100
 1000 ms 57996 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];

bool cmp(int x, int y)
{
    return people[x] <= people[y];
}

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(), cmp);
    }

    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 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 5 ms 9812 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 9940 KB Output is correct
11 Correct 5 ms 9940 KB Output is correct
12 Correct 6 ms 9940 KB Output is correct
13 Correct 5 ms 9940 KB Output is correct
14 Correct 6 ms 9940 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 110 ms 29268 KB Output is correct
4 Correct 110 ms 29052 KB Output is correct
5 Correct 145 ms 32732 KB Output is correct
6 Correct 143 ms 33404 KB Output is correct
7 Correct 157 ms 33564 KB Output is correct
8 Correct 135 ms 29024 KB Output is correct
9 Correct 115 ms 38916 KB Output is correct
10 Correct 123 ms 30272 KB Output is correct
11 Runtime error 84 ms 57996 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 173 ms 35320 KB Output is correct
3 Correct 169 ms 35132 KB Output is correct
4 Correct 127 ms 28968 KB Output is correct
5 Correct 99 ms 29280 KB Output is correct
6 Correct 175 ms 35300 KB Output is correct
7 Correct 117 ms 29044 KB Output is correct
8 Correct 127 ms 29072 KB Output is correct
9 Correct 75 ms 28872 KB Output is correct
10 Correct 97 ms 29012 KB Output is correct
11 Correct 146 ms 30316 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 189 ms 30896 KB Output is correct
3 Correct 187 ms 31608 KB Output is correct
4 Correct 177 ms 32620 KB Output is correct
5 Correct 175 ms 31844 KB Output is correct
6 Correct 165 ms 29508 KB Output is correct
7 Execution timed out 1077 ms 28624 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 35.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 4 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 5 ms 9812 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 9940 KB Output is correct
11 Correct 5 ms 9940 KB Output is correct
12 Correct 6 ms 9940 KB Output is correct
13 Correct 5 ms 9940 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 4 ms 9684 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Correct 110 ms 29268 KB Output is correct
18 Correct 110 ms 29052 KB Output is correct
19 Correct 145 ms 32732 KB Output is correct
20 Correct 143 ms 33404 KB Output is correct
21 Correct 157 ms 33564 KB Output is correct
22 Correct 135 ms 29024 KB Output is correct
23 Correct 115 ms 38916 KB Output is correct
24 Correct 123 ms 30272 KB Output is correct
25 Runtime error 84 ms 57996 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -