제출 #646429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646429		adrilen	Stranded Far From Home (BOI22_island)	C++17	0 / 100	100 ms	19428 KiB

island

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 2e5;

int parent[maxn * 2] = { 0 }, // If the parent is over maxn, it means that that child cannot take over parent
isize[maxn];                  // Size needed to take over that node
ll cursize[maxn];                // The size the node can use to take over other nodes


struct fri {
    int a, b, va, vb;

    bool operator<(const fri &f) const 
    {
        if (va != f.va) return va > f.va;
        return vb > f.vb;
    }
} ;


int find(const int &p)
{
    if (parent[p] >= maxn)
    {
        if (parent[p] - maxn == p) {
            cout << "ERRROR" << endl;
            abort();
        }
        parent[p] = find(parent[p] - maxn) + maxn;
    } else {
        if (parent[p] == p) return p;
        parent[p] = find(parent[p]);
    }

    return parent[p];
}

void merge(int a, int b)
{
    a = find(a), b = find(b);
    if (a >= maxn) a -= maxn;
    if (b >= maxn) b -= maxn;

    if (a == b) return ;

    // a can take b, and b can take a
    if (cursize[a] >= isize[b] && cursize[b] >= isize[a])
    {
        if (cursize[a] < cursize[b]) swap(a, b);

        parent[b] = a;
        cursize[a] += cursize[b];
    } else if (cursize[a] >= isize[b])
    {
        parent[b] = a + maxn; // b can not take a
        cursize[a] += cursize[b];

    } else {
        parent[a] = b + maxn;
        cursize[b] += cursize[a];
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) parent[i] = i;
    for (int i = maxn; i < maxn + n; i++) parent[i] = i - maxn;
    
    // Loading sizes
    for (int i = 0; i < n; i++) {
        cin >> isize[i];
        cursize[i] = isize[i];
    }

    // Loading the edges
    priority_queue <fri> pq;
    int a, b;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        a--; b--;
        if (isize[a] > isize[b]) swap(a, b);

        pq.emplace(fri{a, b, isize[a], isize[b]});
    }

    // Running the algorithm
    fri f;
    while (!pq.empty())
    {
        f = pq.top();
        pq.pop();

        //cout << f.a << " " << f.b << "\n";

        merge(f.b, f.a);
    }

    for (int i = 0; i < n; i++)
    {
        if (parent[i] >= maxn) cout << "0";
        else cout << "1";
    }
    cout << "\n";
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35