oj.uz

Submission #1035650

# Submission time Handle Problem Language Result Execution time Memory
1035650 2024-07-26T12:56:12 Z 12345678 Parachute rings (IOI12_rings) C++17
0 / 100
 606 ms 74668 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;

int n, dsu[nx], deg[nx], c, sz[nx], cy, res;
vector<int> d[nx];
vector<pair<int, int>> edg;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

struct universe
{
    int rt, pa[nx], ans, deg[nx];
    int find(int x)
    {
        if (pa[x]==x) return x;
        return pa[x]=find(pa[x]);
    }
    void merge(int u, int v)
    {
        if (u==rt||v==rt||ans==0) return;
        if (++deg[u]==3) ans=0;
        if (++deg[v]==3) ans=0;
        if (find(u)==find(v)) ans=0;
        else pa[find(u)]=find(v);
    }
    void init()
    {
        ans=1;
        for (int i=0; i<n; i++) pa[i]=i;
        for (auto x:edg) merge(x.first, x.second);
    }
} uni[4];

void Init(int N_) {
    n=N_;
    for (int i=0; i<n; i++) dsu[i]=i;
}

void Link(int A, int B) {
    if (c) for (int i=0; i<4; i++) uni[i].merge(A, B);
    else
    {
        edg.push_back({A, B});
        d[A].push_back(B);
        d[B].push_back(A);
        if (deg[A]+1==3||deg[B]+1==3) c=1;
        if (++deg[A]==3)
        {
            uni[0].rt=A;
            for (int i=0; i<3; i++) uni[1+i].rt=d[A][i];
            for (int i=0; i<4; i++) uni[i].init();
            return;
        }
        if (++deg[B]==3)
        {
            uni[0].rt=B;
            for (int i=0; i<3; i++) uni[1+i].rt=d[B][i];
            for (int i=0; i<4; i++) uni[i].init();
            return;
        }
        if (find(A)!=find(B)) sz[find(A)]+=sz[find(B)], dsu[find(B)]=find(A);
        else res=sz[find(A)], cy++;
    }
}

int CountCritical() {
    if (c&&cy<=1) return uni[0].ans+uni[1].ans+uni[2].ans+uni[3].ans;
    if (cy>1) return 0;
    if (cy==1) return res;
    return n;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 13 ms 24316 KB Output is correct
3 Correct 11 ms 24156 KB Output is correct
4 Incorrect 11 ms 23896 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 50280 KB Output is correct
2 Correct 273 ms 74428 KB Output is correct
3 Correct 169 ms 67408 KB Output is correct
4 Incorrect 606 ms 74668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 13 ms 24316 KB Output is correct
3 Correct 11 ms 24156 KB Output is correct
4 Incorrect 11 ms 23896 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 13 ms 24316 KB Output is correct
3 Correct 11 ms 24156 KB Output is correct
4 Incorrect 11 ms 23896 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 13 ms 24316 KB Output is correct
3 Correct 11 ms 24156 KB Output is correct
4 Incorrect 11 ms 23896 KB Output isn't correct
5 Halted 0 ms 0 KB -