oj.uz

Submission #1091425

# Submission time Handle Problem Language Result Execution time Memory
1091425 2024-09-20T19:59:36 Z ThegeekKnight16 Parachute rings (IOI12_rings) C++17
100 / 100
 1488 ms 256176 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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