답안 #1091425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1091425	2024-09-20T19:59:36 Z	ThegeekKnight16	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	1488 ms	256176 KB

rings

#include <bits/stdc++.h>
using namespace std;
class Dsu
{
protected:
    vector<int> pai, sub, grau;
    bool isCicle;
    int maxGrau;

public:
    Dsu (int N = 0) : pai(N), sub(N, 1), grau(N, 0), isCicle(0), maxGrau(0) {iota(pai.begin(), pai.end(), 0);}

    int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
    void une(int x, int y)
    {
        grau[x]++; grau[y]++;
        maxGrau = max({maxGrau, grau[x], grau[y]});
        x = find(x), y = find(y);
        if (x == y) {isCicle = 1; return;}
        if (sub[x] < sub[y]) swap(x, y);
        pai[y] = x; sub[x] += sub[y];
    }
    bool isGood() {return !isCicle && (maxGrau < 3);}
};

vector<set<int>> grafo;
vector<int> pai, sub, grau;
vector<bool> isCicle;
int critNum = 0, cicleNum = 0, degreeNum = 0, degreeV;
vector<int> tam3;
vector<pair<int, int>> edges;
map<int, Dsu> without;
int N;

void Init(int _N)
{
    N = _N;
    pai.resize(N); iota(pai.begin(), pai.end(), 0);
    sub.resize(N); fill(sub.begin(), sub.end(), 1);
    grau.resize(N); fill(grau.begin(), grau.end(), 0);
    isCicle.resize(N); fill(isCicle.begin(), isCicle.end(), false);
    grafo.clear(); grafo.resize(N); edges.clear(); tam3.clear();
    without.clear();
    critNum = N, cicleNum = 0, degreeNum = 0;
}

int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
void LinkCicle(int A, int B)
{
    if (critNum == 0) return;
    int P = find(A);
    cicleNum -= isCicle[P];
    isCicle[P] = 1;
    cicleNum += isCicle[P];
    if (cicleNum > 1) critNum = 0;
    else critNum = sub[P];
}
void Link3(int A, int B)
{
    if (tam3.size() > 3) {critNum = 0; return;}
    set<int> poss(tam3.begin(), tam3.end());
    for (auto x : tam3)
        for (auto viz : grafo[x])
            poss.insert(viz);

    critNum = 0;
    for (auto x : poss)
    {
        if (!without.count(x))
        {
            without[x] = Dsu(N);
            auto &atual = without[x];
            for (auto [i, j] : edges)
                if (i != x && j != x)
                    atual.une(i, j);
        }
        else if (A != x && B != x) without[x].une(A, B);
        critNum += without[x].isGood();
    }
}
void LinkDegree(int A, int B)
{
    if (A == degreeV || B == degreeV) return;
    without.begin()->second.une(A, B);
    critNum = without.begin()->second.isGood();
}
void buildDegree()
{
    without.clear();
    without[degreeV] = Dsu(N);
    for (auto [A, B] : edges) LinkDegree(A, B);
}

void Link(int A, int B)
{
    edges.emplace_back(A, B);
    if (critNum == 0) return;
    if (degreeNum) {LinkDegree(A, B); return;}
    grafo[A].insert(B), grafo[B].insert(A);

    degreeNum -= (grau[A] >= 4), degreeNum -= (grau[B] >= 4);
    grau[A]++; grau[B]++;
    degreeNum += (grau[A] >= 4), degreeNum += (grau[B] >= 4);
    if (degreeNum > 1) {critNum = 0; return;}
    else if (degreeNum) {degreeV = (grau[A] >= 4 ? A : B); buildDegree(); return;}

    if (grau[A] == 3) tam3.push_back(A);
    if (grau[B] == 3) tam3.push_back(B);
    if (!tam3.empty()) {Link3(A, B); return;}

    int PA = find(A), PB = find(B);
    if (PA == PB) {LinkCicle(A, B); return;}
    if (sub[PA] < sub[PB]) swap(PA, PB);
    pai[PB] = PA; sub[PA] += sub[PB]; isCicle[PA] = (isCicle[PA] || isCicle[PB]);
}

int CountCritical() {return critNum;}

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	440 KB	Output is correct
2	Correct	2 ms	1116 KB	Output is correct
3	Correct	2 ms	1116 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	860 KB	Output is correct
6	Correct	2 ms	1116 KB	Output is correct
7	Correct	1 ms	1116 KB	Output is correct
8	Correct	1 ms	1116 KB	Output is correct
9	Correct	3 ms	1624 KB	Output is correct
10	Correct	3 ms	1628 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	369 ms	90552 KB	Output is correct
2	Correct	408 ms	119476 KB	Output is correct
3	Correct	203 ms	173996 KB	Output is correct
4	Correct	942 ms	174000 KB	Output is correct
5	Correct	965 ms	174256 KB	Output is correct
6	Correct	920 ms	170156 KB	Output is correct
7	Correct	196 ms	173292 KB	Output is correct
8	Correct	1488 ms	228784 KB	Output is correct
9	Correct	1419 ms	256176 KB	Output is correct
10	Correct	626 ms	167732 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	440 KB	Output is correct
2	Correct	2 ms	1116 KB	Output is correct
3	Correct	2 ms	1116 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	860 KB	Output is correct
6	Correct	2 ms	1116 KB	Output is correct
7	Correct	1 ms	1116 KB	Output is correct
8	Correct	1 ms	1116 KB	Output is correct
9	Correct	3 ms	1624 KB	Output is correct
10	Correct	3 ms	1628 KB	Output is correct
11	Correct	3 ms	1628 KB	Output is correct
12	Correct	5 ms	2648 KB	Output is correct
13	Correct	6 ms	3040 KB	Output is correct
14	Correct	2 ms	1624 KB	Output is correct
15	Correct	2 ms	2652 KB	Output is correct
16	Correct	3 ms	2140 KB	Output is correct
17	Correct	2 ms	1884 KB	Output is correct
18	Correct	3 ms	3676 KB	Output is correct
19	Correct	3 ms	2140 KB	Output is correct
20	Correct	7 ms	2928 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	440 KB	Output is correct
2	Correct	2 ms	1116 KB	Output is correct
3	Correct	2 ms	1116 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	860 KB	Output is correct
6	Correct	2 ms	1116 KB	Output is correct
7	Correct	1 ms	1116 KB	Output is correct
8	Correct	1 ms	1116 KB	Output is correct
9	Correct	3 ms	1624 KB	Output is correct
10	Correct	3 ms	1628 KB	Output is correct
11	Correct	3 ms	1628 KB	Output is correct
12	Correct	5 ms	2648 KB	Output is correct
13	Correct	6 ms	3040 KB	Output is correct
14	Correct	2 ms	1624 KB	Output is correct
15	Correct	2 ms	2652 KB	Output is correct
16	Correct	3 ms	2140 KB	Output is correct
17	Correct	2 ms	1884 KB	Output is correct
18	Correct	3 ms	3676 KB	Output is correct
19	Correct	3 ms	2140 KB	Output is correct
20	Correct	7 ms	2928 KB	Output is correct
21	Correct	13 ms	6492 KB	Output is correct
22	Correct	21 ms	10196 KB	Output is correct
23	Correct	30 ms	12712 KB	Output is correct
24	Correct	21 ms	10332 KB	Output is correct
25	Correct	10 ms	11100 KB	Output is correct
26	Correct	21 ms	10588 KB	Output is correct
27	Correct	39 ms	13744 KB	Output is correct
28	Correct	17 ms	11988 KB	Output is correct
29	Correct	18 ms	17036 KB	Output is correct
30	Correct	46 ms	17348 KB	Output is correct

Subtask #5
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	440 KB	Output is correct
2	Correct	2 ms	1116 KB	Output is correct
3	Correct	2 ms	1116 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	860 KB	Output is correct
6	Correct	2 ms	1116 KB	Output is correct
7	Correct	1 ms	1116 KB	Output is correct
8	Correct	1 ms	1116 KB	Output is correct
9	Correct	3 ms	1624 KB	Output is correct
10	Correct	3 ms	1628 KB	Output is correct
11	Correct	369 ms	90552 KB	Output is correct
12	Correct	408 ms	119476 KB	Output is correct
13	Correct	203 ms	173996 KB	Output is correct
14	Correct	942 ms	174000 KB	Output is correct
15	Correct	965 ms	174256 KB	Output is correct
16	Correct	920 ms	170156 KB	Output is correct
17	Correct	196 ms	173292 KB	Output is correct
18	Correct	1488 ms	228784 KB	Output is correct
19	Correct	1419 ms	256176 KB	Output is correct
20	Correct	626 ms	167732 KB	Output is correct
21	Correct	3 ms	1628 KB	Output is correct
22	Correct	5 ms	2648 KB	Output is correct
23	Correct	6 ms	3040 KB	Output is correct
24	Correct	2 ms	1624 KB	Output is correct
25	Correct	2 ms	2652 KB	Output is correct
26	Correct	3 ms	2140 KB	Output is correct
27	Correct	2 ms	1884 KB	Output is correct
28	Correct	3 ms	3676 KB	Output is correct
29	Correct	3 ms	2140 KB	Output is correct
30	Correct	7 ms	2928 KB	Output is correct
31	Correct	13 ms	6492 KB	Output is correct
32	Correct	21 ms	10196 KB	Output is correct
33	Correct	30 ms	12712 KB	Output is correct
34	Correct	21 ms	10332 KB	Output is correct
35	Correct	10 ms	11100 KB	Output is correct
36	Correct	21 ms	10588 KB	Output is correct
37	Correct	39 ms	13744 KB	Output is correct
38	Correct	17 ms	11988 KB	Output is correct
39	Correct	18 ms	17036 KB	Output is correct
40	Correct	46 ms	17348 KB	Output is correct
41	Correct	160 ms	55748 KB	Output is correct
42	Correct	507 ms	142512 KB	Output is correct
43	Correct	145 ms	98384 KB	Output is correct
44	Correct	184 ms	117936 KB	Output is correct
45	Correct	397 ms	169548 KB	Output is correct
46	Correct	592 ms	141952 KB	Output is correct
47	Correct	767 ms	146352 KB	Output is correct
48	Correct	179 ms	164804 KB	Output is correct
49	Correct	563 ms	143280 KB	Output is correct
50	Correct	606 ms	142000 KB	Output is correct
51	Correct	127 ms	84052 KB	Output is correct
52	Correct	161 ms	95088 KB	Output is correct
53	Correct	166 ms	163776 KB	Output is correct
54	Correct	1325 ms	206512 KB	Output is correct
55	Correct	280 ms	94044 KB	Output is correct

답안 #1091425

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