답안 #432761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432761	2021-06-18T13:12:18 Z	JeanBombeur	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	1097 ms	52932 KB

rings

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

//    <|°_°|>

const int MAX_NOEUDS = (1000 * 1000);

int Dsu[4][MAX_NOEUDS];
int Deg[4][MAX_NOEUDS];

pair <int, int> Aretes[MAX_NOEUDS];
int nbAretes = 0;

bool IsCritical[4];
int NoeudOut[4];

int nbNoeuds;
bool isSplit = false;
int tailleCycle = 0;

int Find(int id, int a) {
    if (Dsu[id][a] < 0)
        return a;
    return Dsu[id][a] = Find(id, Dsu[id][a]);
}

bool Union(int id, int nb) {
    int rA = Find(id, Aretes[nb].first), rB = Find(id, Aretes[nb].second);
    if (rA == rB)
        return false;
    if (Dsu[id][rA] > Dsu[id][rB])
        swap(rA, rB);
    Dsu[id][rA] += Dsu[id][rB];
    Dsu[id][rB] = rA;
    return true;
}

void ConstructWithout(int id, int noeud) {
    IsCritical[id] = true;
    NoeudOut[id] = noeud;
    for (int i = 0; i < nbAretes; i ++)
    {
        if (noeud != Aretes[i].first && noeud != Aretes[i].second)
        {
            IsCritical[id] &= Union(id, i);
            IsCritical[id] &= ++ Deg[id][Aretes[i].first] <= 2;
            IsCritical[id] &= ++ Deg[id][Aretes[i].second] <= 2;
        }
    }
    return;
}

void Reconstruct(int a) {
    for (int i = 0; i < nbNoeuds; i ++)
    {
        Deg[0][i] = 0;
        Dsu[0][i] = -1;
    }
    isSplit = true;
    vector <int> nv;
    nv.push_back(a);
    for (int i = 0; i < nbAretes; i ++)
    {
        if (Aretes[i].first == a || Aretes[i].second == a)
            nv.push_back(Aretes[i].second ^ Aretes[i].first ^ a);
    }
    for (int i = 0; i < 4; i ++)
    {
        ConstructWithout(i, nv[i]);
    }
    return;
}

void Init(int n) {
    for (int i = 0; i < 4; i ++)
    {
        for (int j = 0; j < n; j ++)
        {
            Dsu[i][j] = -1;
        }
    }
    nbNoeuds = n;
    return;
}

void Link(int a, int b) {
    Aretes[nbAretes ++] = {a, b};
    if (!isSplit)
    {
        if (Deg[0][a] < Deg[0][b])
            swap(a, b);
        if (!Union(0, nbAretes - 1))
        {
            if (tailleCycle == 0)
                tailleCycle = - Dsu[0][Find(0, a)];
            else
                tailleCycle = -1;
        }
        Deg[0][b] ++;
        if (++ Deg[0][a] == 3)
            Reconstruct(a);
    }
    else
    {
        for (int i = 0; i < 4; i ++)
        {
            if (NoeudOut[i] != a && NoeudOut[i] != b)
            {
                IsCritical[i] &= ++ Deg[i][a] <= 2;
                IsCritical[i] &= ++ Deg[i][b] <= 2;
                IsCritical[i] &= Union(i, nbAretes - 1);
            }
        }
    }
    return;
}

int CountCritical() {
    if (!isSplit)
    {
        if (tailleCycle == 0)
            return nbNoeuds;
        if (tailleCycle > 0)
            return tailleCycle;
        return 0;
    }
    int nb = 0;
    for (int i = 0; i < 4; i ++)
    {
        nb += IsCritical[i];
    }
    return nb;
}

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	588 KB	Output is correct
3	Correct	2 ms	588 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	1 ms	436 KB	Output is correct
8	Correct	1 ms	460 KB	Output is correct
9	Correct	2 ms	588 KB	Output is correct
10	Correct	2 ms	588 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	202 ms	21452 KB	Output is correct
2	Correct	863 ms	42400 KB	Output is correct
3	Correct	1097 ms	51604 KB	Output is correct
4	Correct	468 ms	41136 KB	Output is correct
5	Correct	476 ms	41284 KB	Output is correct
6	Correct	429 ms	40440 KB	Output is correct
7	Correct	1033 ms	50832 KB	Output is correct
8	Correct	940 ms	49492 KB	Output is correct
9	Correct	1004 ms	52932 KB	Output is correct
10	Correct	356 ms	39856 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	588 KB	Output is correct
3	Correct	2 ms	588 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	1 ms	436 KB	Output is correct
8	Correct	1 ms	460 KB	Output is correct
9	Correct	2 ms	588 KB	Output is correct
10	Correct	2 ms	588 KB	Output is correct
11	Correct	2 ms	588 KB	Output is correct
12	Correct	4 ms	844 KB	Output is correct
13	Correct	4 ms	844 KB	Output is correct
14	Correct	3 ms	844 KB	Output is correct
15	Correct	3 ms	1100 KB	Output is correct
16	Correct	3 ms	716 KB	Output is correct
17	Correct	4 ms	908 KB	Output is correct
18	Correct	4 ms	1228 KB	Output is correct
19	Correct	3 ms	716 KB	Output is correct
20	Correct	4 ms	844 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	588 KB	Output is correct
3	Correct	2 ms	588 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	1 ms	436 KB	Output is correct
8	Correct	1 ms	460 KB	Output is correct
9	Correct	2 ms	588 KB	Output is correct
10	Correct	2 ms	588 KB	Output is correct
11	Correct	2 ms	588 KB	Output is correct
12	Correct	4 ms	844 KB	Output is correct
13	Correct	4 ms	844 KB	Output is correct
14	Correct	3 ms	844 KB	Output is correct
15	Correct	3 ms	1100 KB	Output is correct
16	Correct	3 ms	716 KB	Output is correct
17	Correct	4 ms	908 KB	Output is correct
18	Correct	4 ms	1228 KB	Output is correct
19	Correct	3 ms	716 KB	Output is correct
20	Correct	4 ms	844 KB	Output is correct
21	Correct	14 ms	2056 KB	Output is correct
22	Correct	22 ms	3140 KB	Output is correct
23	Correct	27 ms	3780 KB	Output is correct
24	Correct	35 ms	4548 KB	Output is correct
25	Correct	15 ms	3832 KB	Output is correct
26	Correct	34 ms	4864 KB	Output is correct
27	Correct	29 ms	3780 KB	Output is correct
28	Correct	40 ms	4884 KB	Output is correct
29	Correct	29 ms	4516 KB	Output is correct
30	Correct	30 ms	4200 KB	Output is correct

Subtask #5
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	588 KB	Output is correct
3	Correct	2 ms	588 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	1 ms	436 KB	Output is correct
8	Correct	1 ms	460 KB	Output is correct
9	Correct	2 ms	588 KB	Output is correct
10	Correct	2 ms	588 KB	Output is correct
11	Correct	202 ms	21452 KB	Output is correct
12	Correct	863 ms	42400 KB	Output is correct
13	Correct	1097 ms	51604 KB	Output is correct
14	Correct	468 ms	41136 KB	Output is correct
15	Correct	476 ms	41284 KB	Output is correct
16	Correct	429 ms	40440 KB	Output is correct
17	Correct	1033 ms	50832 KB	Output is correct
18	Correct	940 ms	49492 KB	Output is correct
19	Correct	1004 ms	52932 KB	Output is correct
20	Correct	356 ms	39856 KB	Output is correct
21	Correct	2 ms	588 KB	Output is correct
22	Correct	4 ms	844 KB	Output is correct
23	Correct	4 ms	844 KB	Output is correct
24	Correct	3 ms	844 KB	Output is correct
25	Correct	3 ms	1100 KB	Output is correct
26	Correct	3 ms	716 KB	Output is correct
27	Correct	4 ms	908 KB	Output is correct
28	Correct	4 ms	1228 KB	Output is correct
29	Correct	3 ms	716 KB	Output is correct
30	Correct	4 ms	844 KB	Output is correct
31	Correct	14 ms	2056 KB	Output is correct
32	Correct	22 ms	3140 KB	Output is correct
33	Correct	27 ms	3780 KB	Output is correct
34	Correct	35 ms	4548 KB	Output is correct
35	Correct	15 ms	3832 KB	Output is correct
36	Correct	34 ms	4864 KB	Output is correct
37	Correct	29 ms	3780 KB	Output is correct
38	Correct	40 ms	4884 KB	Output is correct
39	Correct	29 ms	4516 KB	Output is correct
40	Correct	30 ms	4200 KB	Output is correct
41	Correct	147 ms	17428 KB	Output is correct
42	Correct	470 ms	39164 KB	Output is correct
43	Correct	262 ms	34892 KB	Output is correct
44	Correct	740 ms	48580 KB	Output is correct
45	Correct	720 ms	45740 KB	Output is correct
46	Correct	382 ms	35400 KB	Output is correct
47	Correct	464 ms	35948 KB	Output is correct
48	Correct	485 ms	42016 KB	Output is correct
49	Correct	389 ms	38172 KB	Output is correct
50	Correct	389 ms	37572 KB	Output is correct
51	Correct	288 ms	31080 KB	Output is correct
52	Correct	609 ms	39692 KB	Output is correct
53	Correct	454 ms	41668 KB	Output is correct
54	Correct	824 ms	44016 KB	Output is correct
55	Correct	1030 ms	47280 KB	Output is correct

답안 #432761

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 14.0 / 14.0

Subtask #5 31.0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
14.0 / 14.0

Subtask #5
31.0 / 31.0