oj.uz

Submission #471543

# Submission time Handle Problem Language Result Execution time Memory
471543 2021-09-09T17:17:02 Z blue Parachute rings (IOI12_rings) C++17
37 / 100
 1634 ms 130304 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)
{
    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';
    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)
            {

                edge[A].push_back(B);
                edge[B].push_back(A);
                go_to_Y(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({});
            }
        }
    }
    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:184:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |         for(int q = 0; q < good.size(); q++)
      |                        ~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 15 ms 24268 KB Output is correct
3 Correct 15 ms 24420 KB Output is correct
4 Correct 15 ms 23912 KB Output is correct
5 Correct 14 ms 24056 KB Output is correct
6 Correct 15 ms 24112 KB Output is correct
7 Correct 14 ms 24140 KB Output is correct
8 Correct 15 ms 24140 KB Output is correct
9 Correct 16 ms 24312 KB Output is correct
10 Correct 16 ms 24420 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 44276 KB Output is correct
2 Correct 1008 ms 92708 KB Output is correct
3 Correct 788 ms 118676 KB Output is correct
4 Correct 850 ms 76372 KB Output is correct
5 Correct 840 ms 76420 KB Output is correct
6 Correct 833 ms 74932 KB Output is correct
7 Correct 777 ms 117516 KB Output is correct
8 Correct 1479 ms 121392 KB Output is correct
9 Correct 1634 ms 130304 KB Output is correct
10 Correct 653 ms 81780 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 15 ms 24268 KB Output is correct
3 Correct 15 ms 24420 KB Output is correct
4 Correct 15 ms 23912 KB Output is correct
5 Correct 14 ms 24056 KB Output is correct
6 Correct 15 ms 24112 KB Output is correct
7 Correct 14 ms 24140 KB Output is correct
8 Correct 15 ms 24140 KB Output is correct
9 Correct 16 ms 24312 KB Output is correct
10 Correct 16 ms 24420 KB Output is correct
11 Correct 20 ms 24308 KB Output is correct
12 Incorrect 18 ms 24964 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 23884 KB Output is correct
2 Correct 15 ms 24268 KB Output is correct
3 Correct 15 ms 24420 KB Output is correct
4 Correct 15 ms 23912 KB Output is correct
5 Correct 14 ms 24056 KB Output is correct
6 Correct 15 ms 24112 KB Output is correct
7 Correct 14 ms 24140 KB Output is correct
8 Correct 15 ms 24140 KB Output is correct
9 Correct 16 ms 24312 KB Output is correct
10 Correct 16 ms 24420 KB Output is correct
11 Correct 20 ms 24308 KB Output is correct
12 Incorrect 18 ms 24964 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 23884 KB Output is correct
2 Correct 15 ms 24268 KB Output is correct
3 Correct 15 ms 24420 KB Output is correct
4 Correct 15 ms 23912 KB Output is correct
5 Correct 14 ms 24056 KB Output is correct
6 Correct 15 ms 24112 KB Output is correct
7 Correct 14 ms 24140 KB Output is correct
8 Correct 15 ms 24140 KB Output is correct
9 Correct 16 ms 24312 KB Output is correct
10 Correct 16 ms 24420 KB Output is correct
11 Correct 325 ms 44276 KB Output is correct
12 Correct 1008 ms 92708 KB Output is correct
13 Correct 788 ms 118676 KB Output is correct
14 Correct 850 ms 76372 KB Output is correct
15 Correct 840 ms 76420 KB Output is correct
16 Correct 833 ms 74932 KB Output is correct
17 Correct 777 ms 117516 KB Output is correct
18 Correct 1479 ms 121392 KB Output is correct
19 Correct 1634 ms 130304 KB Output is correct
20 Correct 653 ms 81780 KB Output is correct
21 Correct 20 ms 24308 KB Output is correct
22 Incorrect 18 ms 24964 KB Output isn't correct
23 Halted 0 ms 0 KB -