oj.uz

답안 #646431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
646431 2022-09-29T19:19:02 Z adrilen Stranded Far From Home (BOI22_island) C++17
0 / 100
 126 ms 14964 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 2e5;

int parent[maxn * 2] = { 0 }, // If the parent is over maxn, it means that that child cannot take over parent
isize[maxn];                  // Size needed to take over that node
ll cursize[maxn];             // The size the node can use to take over other nodes


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] >= maxn)
    {
        if (parent[p] - maxn == p) {
            cout << "ERRROR" << endl;
            abort();
        }
        parent[p] = find(parent[p] - maxn) + maxn;
    } else {
        if (parent[p] == p) return p;
        parent[p] = find(parent[p]);
    }

    return parent[p];
}

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 + maxn; // b can not take a
        cursize[a] += cursize[b];

    } else {
        parent[a] = b + maxn;
        cursize[b] += cursize[a];
    }

}

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;
    for (int i = maxn; i < maxn + n; i++) parent[i] = i - maxn;
    
    // 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++)
    {
        if (find(i) >= maxn) cout << "0";
        else cout << "1";
    }
    cout << "\n";
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 596 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 126 ms 8456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 85 ms 14892 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 80 ms 14964 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 596 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -