oj.uz

Submission #695083

# Submission time Handle Problem Language Result Execution time Memory
695083 2023-02-04T17:25:39 Z finn__ Stranded Far From Home (BOI22_island) C++17
10 / 100
 186 ms 23764 KB 
#include <bits/stdc++.h>
using namespace std;

struct DSU
{
    vector<int64_t> parent, weight;
    vector<bool> is_bad;

    DSU(size_t n, vector<int64_t> const &s)
    {
        parent = vector<int64_t>(n, -1);
        weight = vector<int64_t>(s.begin(), s.end());
        is_bad = vector<bool>(n, 0);
    }

    int root(int u)
    {
        if (parent[u] < 0)
            return u;
        is_bad[u] = is_bad[u] || is_bad[parent[u]];
        return parent[u] = root(parent[u]);
    }

    void merge(int u, int v)
    {
        u = root(u), v = root(v);
        if (u == v)
            return;

        weight[u] += weight[v];
        parent[u] += parent[v];
        parent[v] = u;
    }

    void mark_bad(int u) { is_bad[root(u)] = 1; }

    int64_t component_weight(int u) { return weight[root(u)]; }

    bool get_bad(int u)
    {
        root(u);
        return is_bad[u];
    }
};

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

    size_t n, m;
    cin >> n >> m;

    vector<int64_t> s(n);
    for (int64_t &x : s)
        cin >> x;

    vector<pair<int64_t, unsigned>> nodes(n);
    for (size_t i = 0; i < n; i++)
        nodes[i] = {s[i], i};
    sort(nodes.begin(), nodes.end());

    vector<vector<unsigned>> g(n);
    for (size_t i = 0; i < m; i++)
    {
        unsigned u, v;
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }

    DSU dsu(n, s);

    for (auto const &[x, u] : nodes)
    {
        for (unsigned const &v : g[u])
        {
            if (s[v] <= x)
            {
                if (dsu.component_weight(v) < x)
                    dsu.mark_bad(v);
                dsu.merge(u, v);
            }
        }
    }

    for (size_t i = 0; i < n; i++)
        cout << (unsigned)!dsu.get_bad(i);
    cout << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Incorrect 1 ms 468 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 140 ms 19332 KB Output is correct
4 Correct 140 ms 22360 KB Output is correct
5 Correct 132 ms 22988 KB Output is correct
6 Correct 154 ms 23680 KB Output is correct
7 Correct 134 ms 23764 KB Output is correct
8 Correct 151 ms 23752 KB Output is correct
9 Correct 143 ms 23536 KB Output is correct
10 Correct 94 ms 23624 KB Output is correct
11 Correct 115 ms 23428 KB Output is correct
12 Correct 142 ms 22332 KB Output is correct
13 Correct 118 ms 22264 KB Output is correct
14 Correct 116 ms 22288 KB Output is correct
15 Correct 134 ms 23708 KB Output is correct
16 Correct 76 ms 22764 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 182 ms 19208 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 186 ms 19316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Incorrect 1 ms 468 KB Output isn't correct
10 Halted 0 ms 0 KB -