oj.uz

Submission #252567

# Submission time Handle Problem Language Result Execution time Memory
252567 2020-07-25T21:15:51 Z Kubin Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 105492 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
    {
        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 384 KB Output is correct
2 Correct 362 ms 1016 KB Output is correct
3 Correct 555 ms 1144 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 89 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 543 ms 1144 KB Output is correct
10 Correct 546 ms 1144 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 49224 KB Output is correct
2 Execution timed out 4045 ms 105492 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 384 KB Output is correct
2 Correct 362 ms 1016 KB Output is correct
3 Correct 555 ms 1144 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 89 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 543 ms 1144 KB Output is correct
10 Correct 546 ms 1144 KB Output is correct
11 Execution timed out 4053 ms 1168 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 384 KB Output is correct
2 Correct 362 ms 1016 KB Output is correct
3 Correct 555 ms 1144 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 89 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 543 ms 1144 KB Output is correct
10 Correct 546 ms 1144 KB Output is correct
11 Execution timed out 4053 ms 1168 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 384 KB Output is correct
2 Correct 362 ms 1016 KB Output is correct
3 Correct 555 ms 1144 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 89 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 543 ms 1144 KB Output is correct
10 Correct 546 ms 1144 KB Output is correct
11 Correct 551 ms 49224 KB Output is correct
12 Execution timed out 4045 ms 105492 KB Time limit exceeded
13 Halted 0 ms 0 KB -