oj.uz

Submission #646448

# Submission time Handle Problem Language Result Execution time Memory
646448 2022-09-29T19:58:49 Z adrilen Stranded Far From Home (BOI22_island) C++17
0 / 100
 107 ms 13812 KB 
#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 >= 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; 
        output[b] = true;
        cursize[a] += cursize[b];

    } else {
        parent[a] = b + maxn;
        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();

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

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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Runtime error 2 ms 596 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 107 ms 7648 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 76 ms 13724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 92 ms 13812 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Runtime error 2 ms 596 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -