oj.uz

Submission #252548

# Submission time Handle Problem Language Result Execution time Memory
252548 2020-07-25T20:31:17 Z Kubin Parachute rings (IOI12_rings) C++17
0 / 100
 148 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

struct disjoint_sets
{
    vector<size_t> repr, rank;

    disjoint_sets(size_t n) : repr(n), rank(n)
    {
        for(size_t i = 0; i < n; i++)
            repr[i] = i;
    }

    size_t find(size_t v)
    {
        return v == repr[v] ? v : repr[v] = find(repr[v]);
    }

    bool unite(size_t u, size_t v)
    {
        if((u = repr[u]) == (v = repr[v]))
            return false;
        if(rank[u] > rank[v])
            swap(u, v);
        rank[v] += (rank[u] == rank[v]);
        repr[u] = v;
        return true;
    }
};

struct bamboo_forest
{
    bool ok = true;
    disjoint_sets dsets;
    vector<size_t> deg;

    bamboo_forest(size_t n) : dsets(n), deg(n) {}

    bool edge(size_t u, size_t v)
    {
        if(++deg[u] > 2 or ++deg[v] > 2 or not dsets.unite(u, v))
            return ok = false;
        return true;
    }
};

size_t n;
vector<bamboo_forest> F;

void Init(int _n)
{
    n = _n;
    F.resize(n, bamboo_forest(n));
}

void Link(int u, int v)
{
    for(size_t i = 0; i < n; i++)
        if((size_t)u != i and (size_t)v != i)
            F[i].edge(u, v);
}

int CountCritical()
{
    size_t result = 0;
    for(size_t i = 0; i < n; i++)
        result += F[i].ok;
    return result;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 148 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -