oj.uz

답안 #252567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
252567 2020-07-25T21:15:51 Z Kubin 낙하산 고리들 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -