oj.uz

Submission #471623

# Submission time Handle Problem Language Result Execution time Memory
471623 2021-09-10T04:31:03 Z blue Parachute rings (IOI12_rings) C++17
37 / 100
 1615 ms 124500 KB 
#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(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])
        {
            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])
        {
            edge[A].push_back(A);

            edge[A].push_back(B);
            edge[B].push_back(A);
            go_to_Z(edge[A]);
        }
        else if(cyclic[B] && !cyclic[A])
        {
            edge[B].push_back(B);

            edge[A].push_back(B);
            edge[B].push_back(A);
            go_to_Z(edge[B]);
        }
        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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23844 KB Output is correct
2 Correct 15 ms 24308 KB Output is correct
3 Correct 15 ms 24384 KB Output is correct
4 Correct 15 ms 23908 KB Output is correct
5 Correct 14 ms 24004 KB Output is correct
6 Correct 15 ms 24076 KB Output is correct
7 Correct 14 ms 24172 KB Output is correct
8 Correct 15 ms 24044 KB Output is correct
9 Correct 16 ms 24396 KB Output is correct
10 Correct 16 ms 24400 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 51016 KB Output is correct
2 Correct 1030 ms 100124 KB Output is correct
3 Correct 812 ms 114584 KB Output is correct
4 Correct 883 ms 71076 KB Output is correct
5 Correct 887 ms 71364 KB Output is correct
6 Correct 848 ms 70400 KB Output is correct
7 Correct 800 ms 114104 KB Output is correct
8 Correct 1442 ms 117244 KB Output is correct
9 Correct 1615 ms 124500 KB Output is correct
10 Correct 671 ms 77364 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23844 KB Output is correct
2 Correct 15 ms 24308 KB Output is correct
3 Correct 15 ms 24384 KB Output is correct
4 Correct 15 ms 23908 KB Output is correct
5 Correct 14 ms 24004 KB Output is correct
6 Correct 15 ms 24076 KB Output is correct
7 Correct 14 ms 24172 KB Output is correct
8 Correct 15 ms 24044 KB Output is correct
9 Correct 16 ms 24396 KB Output is correct
10 Correct 16 ms 24400 KB Output is correct
11 Correct 16 ms 24396 KB Output is correct
12 Incorrect 19 ms 24904 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23844 KB Output is correct
2 Correct 15 ms 24308 KB Output is correct
3 Correct 15 ms 24384 KB Output is correct
4 Correct 15 ms 23908 KB Output is correct
5 Correct 14 ms 24004 KB Output is correct
6 Correct 15 ms 24076 KB Output is correct
7 Correct 14 ms 24172 KB Output is correct
8 Correct 15 ms 24044 KB Output is correct
9 Correct 16 ms 24396 KB Output is correct
10 Correct 16 ms 24400 KB Output is correct
11 Correct 16 ms 24396 KB Output is correct
12 Incorrect 19 ms 24904 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23844 KB Output is correct
2 Correct 15 ms 24308 KB Output is correct
3 Correct 15 ms 24384 KB Output is correct
4 Correct 15 ms 23908 KB Output is correct
5 Correct 14 ms 24004 KB Output is correct
6 Correct 15 ms 24076 KB Output is correct
7 Correct 14 ms 24172 KB Output is correct
8 Correct 15 ms 24044 KB Output is correct
9 Correct 16 ms 24396 KB Output is correct
10 Correct 16 ms 24400 KB Output is correct
11 Correct 322 ms 51016 KB Output is correct
12 Correct 1030 ms 100124 KB Output is correct
13 Correct 812 ms 114584 KB Output is correct
14 Correct 883 ms 71076 KB Output is correct
15 Correct 887 ms 71364 KB Output is correct
16 Correct 848 ms 70400 KB Output is correct
17 Correct 800 ms 114104 KB Output is correct
18 Correct 1442 ms 117244 KB Output is correct
19 Correct 1615 ms 124500 KB Output is correct
20 Correct 671 ms 77364 KB Output is correct
21 Correct 16 ms 24396 KB Output is correct
22 Incorrect 19 ms 24904 KB Output isn't correct
23 Halted 0 ms 0 KB -