oj.uz

Submission #252568

# Submission time Handle Problem Language Result Execution time Memory
252568 2020-07-25T21:16:44 Z Kubin Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 94304 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> major;

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)
        major.insert(u);
    if(base.deg[v] > 2)
        major.insert(v);
}

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
    {
        assert(not major.empty());
        size_t result = 0;
        for(size_t i = 0; i < n; i++)
        {
            bamboo_forest re(n);
            for(auto [u, v] : edges)
                if(u != i and v != i)
                    re.edge(u, v);
            result += re.status == Ok;
        }
        return result;
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 359 ms 888 KB Output is correct
3 Correct 545 ms 1028 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 Correct 83 ms 888 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 547 ms 1144 KB Output is correct
10 Correct 542 ms 1024 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 49192 KB Output is correct
2 Execution timed out 4086 ms 94304 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 359 ms 888 KB Output is correct
3 Correct 545 ms 1028 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 Correct 83 ms 888 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 547 ms 1144 KB Output is correct
10 Correct 542 ms 1024 KB Output is correct
11 Execution timed out 4062 ms 1272 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 359 ms 888 KB Output is correct
3 Correct 545 ms 1028 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 Correct 83 ms 888 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 547 ms 1144 KB Output is correct
10 Correct 542 ms 1024 KB Output is correct
11 Execution timed out 4062 ms 1272 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 359 ms 888 KB Output is correct
3 Correct 545 ms 1028 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 Correct 83 ms 888 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 547 ms 1144 KB Output is correct
10 Correct 542 ms 1024 KB Output is correct
11 Correct 574 ms 49192 KB Output is correct
12 Execution timed out 4086 ms 94304 KB Time limit exceeded
13 Halted 0 ms 0 KB -