Submission #580076

#	Time	Username	Problem	Language	Result	Execution time	Memory
580076		Elias	Stranded Far From Home (BOI22_island)	C++17	100 / 100	372 ms	48776 KiB

island

#include <bits/stdc++.h>

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#endif

using namespace std;

#define int int64_t

template <class T>
istream &operator>>(istream &in, vector<T> &v)
{
    for (T &x : v)
        in >> x;
    return in;
}

vector<vector<int>> adj;

struct Boi
{
    int s;
    int i;
    vector<int> members;
    int parent;
    int sum;

    Boi(int s, int i)
    {
        this->s = this->sum = s;
        this->i = this->parent = i;
        members.push_back(i);
    }

    bool operator<(const Boi &other) const
    {
        return s < other.s;
    }
};

vector<Boi> bois;

int find(int i)
{
    if (bois[i].parent == i)
        return i;
    return bois[i].parent = find(bois[i].parent);
}

void mergeVectors(vector<int> &a, vector<int> &b)
{
    if (a.size() < b.size())
        swap(a, b);
    for (int x : b)
        a.push_back(x);
    b = vector<int>(); // empty to save memory
}

void merge(int a, int b)
{
    a = find(a);
    b = find(b);

    if (a == b) // if already in the same group, can be ignored
        return;

    if (bois[b].sum >= bois[a].s) // can take over, and are not taken over
        mergeVectors(bois[a].members, bois[b].members);

    bois[a].sum += bois[b].sum;
    bois[b].parent = a;
}

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

    int n, m;
    cin >> n >> m;

    bois = vector<Boi>(n, Boi(-1, -1));

    for (int i = 0; i < n; i++)
    {
        int s;
        cin >> s;
        bois[i] = Boi(s, i);
    }

    vector<Boi> sorted = bois;

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

    adj = vector<vector<int>>(n);

    while (m--)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (bois[a].s < bois[b].s)
            swap(a, b);
        adj[a].push_back(b); // only to smaller ones
    }

    for (int i = 0; i < n; i++)
        sort(adj[i].begin(), adj[i].end(), [&](int a, int b)
             { return bois[a].s < bois[b].s; });

    for (Boi &boi : sorted)
    {
        for (int c : adj[boi.i])
            merge(boi.i, c);
    }

    int bigBoi = find(sorted.back().i);

    vector<bool> possible(n, false);

    for (int p : bois[bigBoi].members)
        possible[p] = true;

    for (bool b : possible)
    {
        if (b)
            cout << "1";
        else
            cout << "0";
    }
    cout << "\n";
}

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