Submission #646449

#	Time	Username	Problem	Language	Result	Execution time	Memory
646449		adrilen	Stranded Far From Home (BOI22_island)	C++17	0 / 100	130 ms	7676 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] = { 0 }, 
isize[maxn];                  // Size needed to take over that node
ll cursize[maxn];             // The size the node can use to take over other nodes
bool output[maxn] = { 0 };

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] == p) return p;
    int temp = parent[p];
    parent[p] = find(parent[p]);
    
    if (output[temp]) output[p] = true; // Marking the nodes

    return parent[p];
}
int n;
void merge(int a, int b)
{
    a = find(a), b = find(b);

    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; 
        output[b] = true;
        cursize[a] += cursize[b];

    } else {
        parent[a] = b;
        output[a] = true;
        cursize[b] += cursize[a];
    }
    /*
    for (int i = 0; i < n; i++) cout << parent[i] << " ";
    cout << "\n";
    for (int i = 0; i<  n; i++) cout << cursize[i] << " ";
    cout << endl;
    */
}

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

    for (int i = 0; i < n; i++) parent[i] = i;
    
    // 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();

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

    
    for (int i = 0; i < n; i++) {
        find(i);
        cout << !output[i];
    }
    cout << "\n";
}

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