답안 #252574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
252574	2020-07-25T21:25:14 Z	Kubin	낙하산 고리들 (IOI12_rings)	C++17	55 / 100	4000 ms	136384 KB

rings

#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
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	3 ms	896 KB	Output is correct
3	Correct	6 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	2 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	526 ms	49252 KB	Output is correct
2	Correct	3711 ms	113200 KB	Output is correct
3	Correct	1855 ms	136384 KB	Output is correct
4	Correct	1397 ms	94280 KB	Output is correct
5	Correct	1428 ms	94272 KB	Output is correct
6	Correct	1254 ms	92440 KB	Output is correct
7	Correct	1613 ms	134412 KB	Output is correct
8	Correct	1877 ms	110316 KB	Output is correct
9	Correct	2088 ms	117780 KB	Output is correct
10	Correct	834 ms	91716 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	3 ms	896 KB	Output is correct
3	Correct	6 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	2 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	13 ms	1024 KB	Output is correct
12	Correct	12 ms	1588 KB	Output is correct
13	Correct	38 ms	1832 KB	Output is correct
14	Correct	125 ms	1752 KB	Output is correct
15	Correct	167 ms	2744 KB	Output is correct
16	Correct	6 ms	1408 KB	Output is correct
17	Correct	62 ms	2564 KB	Output is correct
18	Correct	24 ms	2584 KB	Output is correct
19	Correct	6 ms	1408 KB	Output is correct
20	Correct	42 ms	1596 KB	Output is correct

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	3 ms	896 KB	Output is correct
3	Correct	6 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	2 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	13 ms	1024 KB	Output is correct
12	Correct	12 ms	1588 KB	Output is correct
13	Correct	38 ms	1832 KB	Output is correct
14	Correct	125 ms	1752 KB	Output is correct
15	Correct	167 ms	2744 KB	Output is correct
16	Correct	6 ms	1408 KB	Output is correct
17	Correct	62 ms	2564 KB	Output is correct
18	Correct	24 ms	2584 KB	Output is correct
19	Correct	6 ms	1408 KB	Output is correct
20	Correct	42 ms	1596 KB	Output is correct
21	Correct	23 ms	4216 KB	Output is correct
22	Correct	42 ms	6384 KB	Output is correct
23	Correct	47 ms	7916 KB	Output is correct
24	Execution timed out	4083 ms	9348 KB	Time limit exceeded
25	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	896 KB	Output is correct
3	Correct	6 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	2 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	526 ms	49252 KB	Output is correct
12	Correct	3711 ms	113200 KB	Output is correct
13	Correct	1855 ms	136384 KB	Output is correct
14	Correct	1397 ms	94280 KB	Output is correct
15	Correct	1428 ms	94272 KB	Output is correct
16	Correct	1254 ms	92440 KB	Output is correct
17	Correct	1613 ms	134412 KB	Output is correct
18	Correct	1877 ms	110316 KB	Output is correct
19	Correct	2088 ms	117780 KB	Output is correct
20	Correct	834 ms	91716 KB	Output is correct
21	Correct	13 ms	1024 KB	Output is correct
22	Correct	12 ms	1588 KB	Output is correct
23	Correct	38 ms	1832 KB	Output is correct
24	Correct	125 ms	1752 KB	Output is correct
25	Correct	167 ms	2744 KB	Output is correct
26	Correct	6 ms	1408 KB	Output is correct
27	Correct	62 ms	2564 KB	Output is correct
28	Correct	24 ms	2584 KB	Output is correct
29	Correct	6 ms	1408 KB	Output is correct
30	Correct	42 ms	1596 KB	Output is correct
31	Correct	23 ms	4216 KB	Output is correct
32	Correct	42 ms	6384 KB	Output is correct
33	Correct	47 ms	7916 KB	Output is correct
34	Execution timed out	4083 ms	9348 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-

답안 #252574

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 0 / 14.0

Subtask #5 0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
0 / 14.0

Subtask #5
0 / 31.0