Submission #471628

#	Time	Username	Problem	Language	Result	Execution time	Memory
471628		blue	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	1680 ms	118420 KiB

rings

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

const int maxN = 1'000'000;

struct disjoint_set
{
    int S;
    vector<int> parent;
    vector<int> subtree;

    disjoint_set()
    {
        ;
    }

    disjoint_set(int s)
    {
        S = s;
        parent = vector<int>(S);
        subtree = vector<int>(S);
        for(int i = 0; i < S; i++)
        {
            parent[i] = i;
            subtree[i] = 1;
        }
    }

    int root(int u)
    {
        int v = u;
        while(parent[v] != v) v = parent[v];
        parent[u] = v;
        return v;
    }

    bool connected(int u, int v)
    {
        return root(u) == root(v);
    }

    void join(int u, int v)
    {
        u = root(u);
        v = root(v);
        if(u == v) return;
        if(subtree[u] < subtree[v]) swap(u, v);

        subtree[u] += subtree[v];
        parent[v] = u;
    }
};

const int X = 0;
const int Y = 1;
const int Z = 2;


//general
int state = X;
int N;

//state == X
vector<int> edge[maxN];
disjoint_set prevDSU;

int degree(int u)
{
    return (int)edge[u].size();
}



//state == Y
int cyclic_count = 0;
vector<bool> cyclic(maxN, 0);

void go_to_Y(int label)
{
    // cerr << "switching to Y\n";
    state = Y;

    for(int i = 0; i < N; i++)
    {
        if(prevDSU.connected(i, label))
        {
            cyclic[i] = 1;
            cyclic_count++;
        }
    }
}



//state == Z

int Zsize;
vector<int> Z_critical;
vector< vector<int> > Z_degree;
vector<disjoint_set> DSU;
vector<bool> good;

void Z_link(int A, int B)
{
    for(int q = 0; q < Zsize; q++)
    {
        if(!good[q]) continue;

        int z = Z_critical[q];

        if(A == z || B == z)
        {
            continue;
        }
        // cerr << "link " << A << ' ' << B << " in DSU " << q << " ( " << Z_critical[q] << ") \n";
        // cerr << DSU[q].root(A) << ' ' << DSU[q].root(B) << '\n';

        if(DSU[q].connected(A, B))
        {
            // cerr << "DSU " << q << " (" << Z_critical[q] << ") made not good by cycle\n";
            good[q] = 0;
        }
        Z_degree[q][A]++;
        Z_degree[q][B]++;
        // if(q == 0)
        //     cerr << "edge " << A << ' ' << B << '\n';
        if(Z_degree[q][A] > 2 || Z_degree[q][B] > 2)
        {
            // cerr << "DSU " << q << " (" << Z_critical[q] << ") made not good by high degree\n";
            good[q] = 0;
        }

        DSU[q].join(A, B);
    }
}

void go_to_Z(vector<int> V)
{
    // cerr << "switching to Z\n";
    // for(int v:V) cerr << v << ' ';
    // cerr << '\n';
    // cerr << (int)V.size() << '\n';
    state = Z;

    Zsize = V.size();
    Z_critical = V;
    Z_degree = vector< vector<int> >(Zsize, vector<int>(N, 0));
    DSU = vector<disjoint_set>(Zsize, disjoint_set(N));
    good = vector<bool>(Zsize, 1);

    for(int u = 0; u < N; u++)
    {
        for(int v: edge[u])
        {
            // cerr << "edge list " << u << ' ' << v << '\n';
            if(v < u) continue;
            Z_link(u, v);
        }
    }

    // for(int q = 0; q < 4; q++)
    // {
    //     for(int i = 0; i < N; i++) cerr << Z_degree[q][i] << ' ';
    //     cerr << '\n';
    // }
}




void Init(int N_)
{
    N = N_;
    prevDSU = disjoint_set(N);
}


int CountCritical()
{
    if(state == X) return N;
    else if(state == Y)
    {
        return cyclic_count;
    }
    else// if(state == Z)
    {
        int res = 0;
        for(int q = 0; q < good.size(); q++)
        {
            res += good[q];
            // if(good[q]) cerr << "good = " << Z_critical[q] << '\n';
        }

        return res;
    }
}

void Link(int A, int B)
{


    if(state == X)
    {
        if(!prevDSU.connected(A, B))
        {
            if(degree(A) <= 1 && degree(B) <= 1)
            {
                prevDSU.join(A, B);

                edge[A].push_back(B);
                edge[B].push_back(A);
            }
            else if(degree(A) <= 1)
            {
                vector<int> V = edge[B];
                V.push_back(A);
                V.push_back(B);

                edge[A].push_back(B);
                edge[B].push_back(A);
                go_to_Z(V);
            }
            else if(degree(B) <= 1)
            {
                vector<int> V = edge[A];
                V.push_back(A);
                V.push_back(B);

                edge[A].push_back(B);
                edge[B].push_back(A);
                go_to_Z(V);
            }
            else
            {

                edge[A].push_back(B);
                edge[B].push_back(A);
                go_to_Z({A, B});
            }
        }
        else
        {
            if(degree(A) <= 1 && degree(B) <= 1)
            {
                // cerr << "case U\n";
                edge[A].push_back(B);
                edge[B].push_back(A);
                go_to_Y(A);
            }
            else if(degree(A) <= 1)
            {
                // cerr << "case V\n";
                vector<int> V = edge[B];
                V.push_back(A);
                V.push_back(B);

                edge[A].push_back(B);
                edge[B].push_back(A);
                go_to_Z(V);
            }
            else if(degree(B) <= 1)
            {
                // cerr << "case W\n";
                vector<int> V = edge[A];
                V.push_back(A);
                V.push_back(B);

                edge[A].push_back(B);
                edge[B].push_back(A);
                go_to_Z(V);
            }
            else
            {
                // cerr << "case T\n";


                vector<int> V{A, B};
                for(int e: edge[A])
                    for(int f: edge[B])
                        if(e == f)
                            V.push_back(e);

                edge[A].push_back(B);
                edge[B].push_back(A);
                go_to_Z(V);
            }
        }
    }
    else if(state == Y)
    {
        if(cyclic[A] && cyclic[B])
        {
            edge[A].push_back(B);
            edge[B].push_back(A);
            go_to_Z({A, B});
        }
        else if(cyclic[A] && !cyclic[B])
        {
            vector<int> V = edge[A];
            V.push_back(A);

            edge[A].push_back(B);
            edge[B].push_back(A);
            go_to_Z(V);
        }
        else if(cyclic[B] && !cyclic[A])
        {
            vector<int> V = edge[B];
            V.push_back(B);

            edge[A].push_back(B);
            edge[B].push_back(A);
            go_to_Z(V);
        }
        else
        {
            if(!prevDSU.connected(A, B))
            {
                if(degree(A) <= 1 && degree(B) <= 1)
                {

                    edge[A].push_back(B);
                    edge[B].push_back(A);
                    prevDSU.join(A, B);
                }
                else
                {

                    edge[A].push_back(B);
                    edge[B].push_back(A);
                    go_to_Z({});
                }
            }
            else
            {

                edge[A].push_back(B);
                edge[B].push_back(A);
                go_to_Z({});
            }
        }
    }
    else if(state == Z)
    {
        edge[A].push_back(B);
        edge[B].push_back(A);
        Z_link(A, B);
    }

    // cerr << CountCritical() << '\n';
}

Compilation message (stderr)

rings.cpp: In function 'int CountCritical()':
rings.cpp:189:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |         for(int q = 0; q < good.size(); q++)
      |                        ~~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31