Submission #471617

#	Time	Username	Problem	Language	Result	Execution time	Memory
471617		blue	Parachute rings (IOI12_rings)	C++17	0 / 100	15 ms	18332 KiB

rings

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

const int maxN = 20'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;
    }

    void reset()
    {
        for(int i = 0; i < S; i++)
        {
            parent[i] = i;
            subtree[i] = 1;
        }
    }
};





int N;
vector<int> edge[maxN];
int edge_count = 0;

vector<int> cyclic(maxN, 0);
int cyclic_count = 0;

disjoint_set DSU;

disjoint_set temp;

void Init(int N_)
{
    N = N_;

    DSU = disjoint_set(N);
    temp = disjoint_set(N);
}

void Link(int A, int B)
{
    edge[A].push_back(B);
    edge[B].push_back(A);

    if(DSU.connected(A, B) && !cyclic[ DSU.root(A) ])
    {
        cyclic[ DSU.root(A) ] = 1;
        cyclic_count++;
    }

    edge_count++;
}



int CountCritical()
{
    vector<int> bad, very_bad;
    for(int i = 0; i < N; i++)
    {
        if((int)edge[i].size() == 3)
            bad.push_back(i);
        else if((int)edge[i].size() >= 4)
            very_bad.push_back(i);
    }

    if((int)very_bad.size() >= 2)
        return 0;
    else if(very_bad.size() == 1)
        bad = very_bad;

    if(bad.size() >= 1) //build a new graph.
    {
        // cerr << "case X\n";
        // cerr << "case 1\n";
        vector<int> badset;
        for(int i = 0; i < N; i++)
        {
            int ct = 0;
            if(edge[i].size() >= 3)
                ct++;
            for(int j: edge[i])
                if(edge[j].size() >= 3)
                    ct++;

            if(ct == bad.size())
                badset.push_back(i);
        }
        // for(int b: badset) cerr << b << ' ';
        // cerr << '\n';

        int res = 0;
        for(int B: badset)
        {
            int good = 1;
            temp.reset();
            vector<int> deg(N, 0);
            for(int u = 0; u < N; u++)
            {
                for(int v: edge[u])
                {
                    if(v < u) continue;
                    if(u == B || v == B) continue;
                    if(temp.connected(u, v))
                        good = 0;
                    temp.join(u, v);
                    deg[u]++;
                    deg[v]++;

                    if(deg[u] >= 3 || deg[v] >= 3)
                        good = 0;
                }
            }
            res += good;
        }
        return res;
    }
    else// if(bad.size() == 0) //cycles and chains, if 0 cycles return N, else return size of the cycle.
    {
        if(cyclic_count == 0) return N;
        else
        {
            int res = 0;
            for(int i = 0; i < N; i++)
                if(cyclic[ DSU.root(i) ])
                    res++;
            return res;
        }
    }
}

Compilation message (stderr)

rings.cpp: In function 'int CountCritical()':
rings.cpp:133:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |             if(ct == bad.size())
      |                ~~~^~~~~~~~~~~~~

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