oj.uz

답안 #730289

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
730289 2023-04-25T15:14:24 Z pls33 Stranded Far From Home (BOI22_island) C++17
0 / 100
 171 ms 21456 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
template <typename F>
void _debug(F f)
{
    f();
}

#ifndef _AAAAAAAAA
#define debug(x)
#else
#define debug(x) _debug(x)
#endif
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion

using state_t = bitset<(int)2e5>;

struct dsu_t
{
    vi32 parent;
    vi32 size;
    vi64 weight;
    state_t marked;

    dsu_t(int n) : parent(n), size(n, 1), weight(n)
    {
        iota(parent.begin(), parent.end(), 0);
    }

    int find_set(int a)
    {
        if (parent[a] == a)
        {
            return a;
        }

        parent[a] = find_set(parent[a]);
        if (marked[parent[a]])
        {
            marked[a] = true;
        }

        return parent[a];
    }

    void unite(int a, int b)
    {
        a = find_set(a);
        b = find_set(b);

        if (a == b)
        {
            return;
        }

        if ((weight[a] == weight[b])
                ? (size[a] < size[b])
                : (weight[a] < weight[b]))
        {
            swap(a, b);
        }

        parent[b] = a;
        size[a] += size[b];
        weight[a] += weight[b];
    }
};

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("sala.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int v, e;
    cin >> v >> e;

    vi64 weight(v);
    for (auto &w : weight)
    {
        cin >> w;
    }

    vi32 order(v);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(),
         [&](int a, int b)
         {
             return weight[a] < weight[b];
             //
         });

    vvi32 adj(v);
    for (int i = 0; i < e; i++)
    {
        int a, b;
        cin >> a >> b;

        a--;
        b--;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dsu_t dsu(v);
    dsu.weight = weight;

    for (auto &i : order)
    {
        for (auto &next : adj[i])
        {
            next = dsu.find_set(next);

            if (dsu.weight[next] > weight[i])
            {
                continue;
            }

            if (dsu.weight[next] < weight[i])
            {
                dsu.marked[next] = true;
            }

            dsu.unite(next, i);
        }
    }

    for (int i = 0; i < v; i++)
    {
        dsu.find_set(i);
        cout << !dsu.marked[i];
    }
    cout << '\n';

    return 0;
}

Compilation message

island.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
island.cpp:43: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   43 | #pragma endregion
      |

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 143 ms 21456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 171 ms 21288 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 165 ms 21444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -