oj.uz

Submission #252573

# Submission time Handle Problem Language Result Execution time Memory
252573 2020-07-25T21:24:47 Z Kubin Parachute rings (IOI12_rings) C++17
0 / 100
 3471 ms 136264 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 = find(u)) == (v = find(v)))
            return false;
        if(rank[u] > rank[v])
            swap(u, v);
        rank[v] += (rank[u] == rank[v]);
        repr[u] = v;
        return true;
    }
};

enum BambooForestStatus
{
    Ok,
    Cycles,
    Bad
};

struct bamboo_forest
{
    BambooForestStatus status = Ok;
    disjoint_sets dsets;
    vector<size_t> deg;
    size_t cycles = 0;

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

    BambooForestStatus edge(size_t u, size_t v)
    {
        deg[u]++; deg[v]++;
        if(deg[u] > 2 or deg[v] > 2)
            status = Bad;
        if((status == Ok or status == Cycles) and dsets.find(u) == dsets.find(v) and deg[u] == 2 and deg[v] == 2)
            status = Cycles, cycles++;
        else if(not dsets.unite(u, v))
            status = Bad;
        return status;
    }
};

size_t n;
vector<pair<size_t, size_t>> edges;
vector<vector<size_t>> graph;
bamboo_forest base;
size_t first_cycle_size;
unordered_set<size_t> greater2, greater3;

size_t w3 = SIZE_MAX;
bamboo_forest drop_w3;

void Init(int _n)
{
    n = _n;
    base = bamboo_forest(n);
    graph.resize(n);
}

void Link(int u, int v)
{
    edges.emplace_back(u, v);
    graph[u].push_back(v);
    graph[v].push_back(u);

    auto pre = base.status;
    base.edge(u, v);

    if(pre == Ok and base.status == Cycles and base.cycles == 1)
    {
        auto w = base.dsets.find(u);
        for(size_t i = 0; i < n; i++)
            if(base.dsets.find(i) == w)
                first_cycle_size++;
    }
    if(base.deg[u] > 2) greater2.insert(u);
    if(base.deg[v] > 2) greater2.insert(v);
    if(base.deg[u] > 3) greater3.insert(u);
    if(base.deg[v] > 3) greater3.insert(v);

    if(not greater3.empty() and w3 == SIZE_MAX)
    {
        w3 = *greater3.begin();
        drop_w3 = bamboo_forest(n);
        for(auto [uu, vv] : edges)
            if(uu != w3 and vv != w3)
                drop_w3.edge(uu, vv);
    }
    else if(w3 != SIZE_MAX)
        drop_w3.edge(u, v);
}

bool naive_try(size_t i)
{
    bamboo_forest re(n);
    for(auto [u, v] : edges)
        if(u != i and v != i)
            re.edge(u, v);
    return re.status == Ok;
}

int CountCritical()
{
    if(base.status == Ok)
        return n;
    else if(base.status == Cycles and base.cycles == 1)
        return first_cycle_size;
    else if(base.status == Cycles and base.cycles > 1)
        return 0;
    else if(greater3.size() > 1)
        return 0;
    else
    {
        if(greater3.empty())
            return drop_w3.status == Ok;

        size_t result = 0, w = *greater2.begin();
        for(size_t i : graph[w])
            result += naive_try(i);
        result += naive_try(w);
        return result;
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 8 ms 1152 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Incorrect 1 ms 640 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 49236 KB Output is correct
2 Correct 3471 ms 113188 KB Output is correct
3 Correct 1861 ms 136264 KB Output is correct
4 Correct 1589 ms 94144 KB Output is correct
5 Correct 1446 ms 94272 KB Output is correct
6 Correct 1446 ms 92512 KB Output is correct
7 Correct 1794 ms 134268 KB Output is correct
8 Incorrect 1259 ms 88364 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 8 ms 1152 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Incorrect 1 ms 640 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 8 ms 1152 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Incorrect 1 ms 640 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 8 ms 1152 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Incorrect 1 ms 640 KB Output isn't correct
8 Halted 0 ms 0 KB -