oj.uz

답안 #252570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
252570 2020-07-25T21:20:47 Z Kubin 낙하산 고리들 (IOI12_rings) C++17
37 / 100
 4000 ms 117872 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;

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);
}

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
    {
        size_t result = 0;
        size_t w = greater3.empty() ? *greater2.begin() : *greater3.begin();
        for(size_t i : graph[w])
            result += naive_try(i);
        result += naive_try(w);
        return result;
    }
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 5 ms 1024 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 1 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 494 ms 49220 KB Output is correct
2 Correct 3438 ms 94460 KB Output is correct
3 Correct 1510 ms 112876 KB Output is correct
4 Correct 1345 ms 94272 KB Output is correct
5 Correct 1265 ms 94564 KB Output is correct
6 Correct 1384 ms 92736 KB Output is correct
7 Correct 1537 ms 110936 KB Output is correct
8 Correct 2159 ms 110336 KB Output is correct
9 Correct 2374 ms 117872 KB Output is correct
10 Correct 846 ms 91588 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 5 ms 1024 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 1 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 14 ms 1024 KB Output is correct
12 Correct 11 ms 1604 KB Output is correct
13 Correct 38 ms 1612 KB Output is correct
14 Execution timed out 4054 ms 1780 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 5 ms 1024 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 1 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 14 ms 1024 KB Output is correct
12 Correct 11 ms 1604 KB Output is correct
13 Correct 38 ms 1612 KB Output is correct
14 Execution timed out 4054 ms 1780 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 5 ms 1024 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 1 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 494 ms 49220 KB Output is correct
12 Correct 3438 ms 94460 KB Output is correct
13 Correct 1510 ms 112876 KB Output is correct
14 Correct 1345 ms 94272 KB Output is correct
15 Correct 1265 ms 94564 KB Output is correct
16 Correct 1384 ms 92736 KB Output is correct
17 Correct 1537 ms 110936 KB Output is correct
18 Correct 2159 ms 110336 KB Output is correct
19 Correct 2374 ms 117872 KB Output is correct
20 Correct 846 ms 91588 KB Output is correct
21 Correct 14 ms 1024 KB Output is correct
22 Correct 11 ms 1604 KB Output is correct
23 Correct 38 ms 1612 KB Output is correct
24 Execution timed out 4054 ms 1780 KB Time limit exceeded
25 Halted 0 ms 0 KB -