Submission #258796

#	Time	Username	Problem	Language	Result	Execution time	Memory
258796		SamAnd	Parachute rings (IOI12_rings)	C++17	55 / 100	4077 ms	87404 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 1000006;

int n;
vector<int> g[N];

int c[N];

int k;
void dfs(int x)
{
    c[x] = k;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (!c[h])
            dfs(h);
    }
}

bool cc[N];

bool stg(int r)
{
    for (int x = 1; x <= n; ++x)
    {
        if (x == r)
            continue;
        int q = 0;
        for (int i = 0; i < g[x].size(); ++i)
        {
            int h = g[x][i];
            if (h == r)
                continue;
            ++q;
        }
        if (q >= 3)
            return false;
    }

    memset(c, 0, sizeof c);
    k = 0;
    c[r] = -1;
    for (int x = 1; x <= n; ++x)
    {
        if (!c[x])
        {
            ++k;
            dfs(x);
        }
    }

    memset(cc, false, sizeof cc);
    for (int x = 1; x <= n; ++x)
    {
        if (x == r)
            continue;
        int q = 0;
        for (int i = 0; i < g[x].size(); ++i)
        {
            int h = g[x][i];
            if (h == r)
                continue;
            ++q;
        }
        if (q <= 1)
            cc[c[x]] = true;
    }
    for (int i = 1; i <= k; ++i)
    {
        if (cc[i] == false)
            return false;
    }
    return true;
}

int solv0()
{
    /*int ans = 0;
    for (int x = 1; x <= n; ++x)
    {
        if (stg(x))
            ++ans;
    }
    return ans;*/

    for (int x = 1; x <= n; ++x)
    {
        if (sz(g[x]) >= 4)
        {
            if (stg(x))
                return 1;
            return 0;
        }
    }
    for (int x = 1; x <= n; ++x)
    {
        if (sz(g[x]) == 3)
        {
            int ans = 0;
            if (stg(x))
                ++ans;
            for (int i = 0; i < g[x].size(); ++i)
            {
                int h = g[x][i];
                if (stg(h))
                    ++ans;
            }
            return ans;
        }
    }

    memset(c, 0, sizeof c);
    k = 0;
    for (int x = 1; x <= n; ++x)
    {
        if (!c[x])
        {
            ++k;
            dfs(x);
        }
    }

    memset(cc, false, sizeof cc);
    for (int x = 1; x <= n; ++x)
    {
        if (sz(g[x]) <= 1)
            cc[c[x]] = true;
    }

    int qf = 0;
    for (int i = 1; i <= k; ++i)
    {
        if (cc[i] == false)
            ++qf;
    }
    if (qf >= 2)
        return 0;
    if (qf == 1)
    {
        int ans = 0;
        for (int x = 1; x <= n; ++x)
        {
            if (cc[c[x]] == false)
                ++ans;
        }
        return ans;
    }
    return n;
}

void Init(int N_)
{
    n = N_;
}

void Link(int x, int y)
{
    ++x;
    ++y;
    g[x].push_back(y);
    g[y].push_back(x);
}

int CountCritical()
{
    return solv0();
}

Compilation message (stderr)

rings.cpp: In function 'void dfs(int)':
rings.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
rings.cpp: In function 'bool stg(int)':
rings.cpp:36:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
rings.cpp:65:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
rings.cpp: In function 'int solv0()':
rings.cpp:109:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < g[x].size(); ++i)
                             ~~^~~~~~~~~~~~~

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