oj.uz

Submission #580074

# Submission time Handle Problem Language Result Execution time Memory
580074 2022-06-20T14:27:43 Z Elias Stranded Far From Home (BOI22_island) C++17
30 / 100
 325 ms 48880 KB 
#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 = 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Incorrect 2 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 182 ms 46012 KB Output is correct
4 Incorrect 176 ms 46080 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 248 ms 46932 KB Output is correct
3 Correct 274 ms 47452 KB Output is correct
4 Incorrect 183 ms 45204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 275 ms 45740 KB Output is correct
3 Correct 325 ms 46436 KB Output is correct
4 Correct 263 ms 47308 KB Output is correct
5 Correct 244 ms 48276 KB Output is correct
6 Correct 261 ms 45084 KB Output is correct
7 Correct 183 ms 45548 KB Output is correct
8 Correct 138 ms 45512 KB Output is correct
9 Correct 177 ms 24784 KB Output is correct
10 Correct 250 ms 48880 KB Output is correct
11 Correct 223 ms 46380 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Incorrect 2 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -