oj.uz

Submission #646966

# Submission time Handle Problem Language Result Execution time Memory
646966 2022-10-01T08:51:31 Z adrilen Stranded Far From Home (BOI22_island) C++17
10 / 100
 170 ms 21568 KB 
#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;

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

    parent[p] = find(parent[p]);
    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
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 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Incorrect 2 ms 468 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 138 ms 21536 KB Output is correct
4 Correct 128 ms 20112 KB Output is correct
5 Correct 159 ms 20860 KB Output is correct
6 Correct 152 ms 18868 KB Output is correct
7 Correct 167 ms 18756 KB Output is correct
8 Correct 156 ms 18764 KB Output is correct
9 Correct 151 ms 18632 KB Output is correct
10 Correct 109 ms 19524 KB Output is correct
11 Correct 133 ms 19328 KB Output is correct
12 Correct 149 ms 18828 KB Output is correct
13 Correct 131 ms 18688 KB Output is correct
14 Correct 139 ms 18720 KB Output is correct
15 Correct 137 ms 18596 KB Output is correct
16 Correct 89 ms 18384 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Incorrect 158 ms 21452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.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 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Incorrect 2 ms 468 KB Output isn't correct
15 Halted 0 ms 0 KB -