Submission #646967

#	Time	Username	Problem	Language	Result	Execution time	Memory
646967		adrilen	Stranded Far From Home (BOI22_island)	C++17	100 / 100	230 ms	25912 KiB

island

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

int isize[maxn], parent[maxn];
ll cursize[maxn];
bool marked[maxn] = { 0 };

int find(const int &p)
{
    if (p == parent[p]) return p;

    int last = parent[p];
    parent[p] = find(parent[p]);

    if (marked[last]) marked[p] = true;

    return parent[p];
}

void merge(int d, int b)        // a is newly inserted node, b is old
{
    int a;
    a = find(d), b = find(b);

    if (a == b) return ;


    // a will allways take b, but b will not allways take a

    // printf("%d %d %d %d\n", a, b, cursize[b], isize[a]);
    if (cursize[b] >= isize[d])
    {
        // Both will take each other
        cursize[b] += cursize[a];
        parent[a] = b;
    } else {
        cursize[a] += cursize[b];
        parent[b] = a;
        marked[b] = true;
    }

}


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;

    vector <pii> pq(n);
    for (int i = 0; i < n; i++) {
        cin >> isize[i];
        cursize[i] = isize[i];
        pq[i] = pii(isize[i], i);
    }

    sort(pq.begin(), pq.end());

    vector <vector <int>> adj(n);
    int a, b;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        a--; b--;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }

    vector <int> created(n);

    auto it = pq.begin();
    int pos;
    while (it != pq.end())
    {
        pos = (*it).second;
        it++;

        created[pos] = true;

        for (int nei : adj[pos])
        {
            if (!created[nei]) continue;

            merge(pos, nei);
        }
    }


    for (int i = 0; i < n; i++) find(i);

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

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