Submission #361870

#	Time	Username	Problem	Language	Result	Execution time	Memory
361870		idk321	Parachute rings (IOI12_rings)	C++11	0 / 100	150 ms	262148 KiB

rings

#include <vector>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef long long ll;



const int N = 5005;
const int X = 5005;
bool all = true;
bool bad = false;
bool bad2[X];
vector<int> big3;
vector<int> adj[X][N];
int p[X][N];
//int r[3][N];
bool second = false;

int n;

int getR(int x, int a)
{
    if (p[x][a] == a)return a;
    p[x][a] = getR(x, p[x][a]);
    return p[x][a];
}

void join(int x, int a, int b)
{
    a = getR(x, a);
    b = getR(x, b);
    if (a == b) return;
    p[x][a] = b;
}


bool vis[N];
bool onSt[N];
vector<int> st;
vector<int> cycle;
void getCycle(int node, int par)
{
    vis[node] = true;
    onSt[node] = true;
    st.push_back(node);
    for (int next : adj[0][node])
    {
        if (next == par || (vis[next] && !onSt[next])) continue;
        if (onSt[next])
        {
            auto it = st.rbegin();
            while (*it != next)
            {
                cycle.push_back(*it);
                it++;
            }
            cycle.push_back(next);
        } else
        {
            getCycle(next, node);
        }
    }

    st.pop_back();
    onSt[node] = false;
}

void Init(int n_) {
    n = n_;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < X; j++) p[j][i] = i;
    }

}

void Link(int a, int b) {
    if (bad) return;

    if (big3.size() <= X - 1 && !big3.empty())
    {
        second = true;

        for (int l = 1; l <= X - 1; l++)
        {
            if (bad2[l]) continue;
            if (a == big3[l - 1] || b == big3[l - 1]) continue;
            adj[l][a].push_back(b);
            adj[l][b].push_back(a);
            if (getR(l, a) == getR(l, b))
            {

                bad2[l] = true;
                continue;
            }
            join(l, a, b);

            for (int t = 0; t < 2; t++)
            {
                swap(a, b);

                if (adj[l][a].size() >= 3)
                {
                    bad2[l] = true;
                    continue;
                }
            }
        }
    } else
    {

        adj[0] [a].push_back(b);
        adj[0] [b].push_back(a);
        if (getR(0, a) == getR(0, b) && cycle.empty())
        {
            all = false;


            getCycle(a, -1);

            if (big3.empty()) big3 = cycle;
            else
            {
                vector<int> n3;

                for (int i : cycle)
                {
                    for (int j : big3) if (i == j) n3.push_back(i);
                }

                big3 = n3;
            }
        }

        join(0, a, b);
        for (int t = 0; t < 2; t++)
        {
            swap(a, b);
            if (adj[0] [a].size() >= 3)
            {
                all = false;
                if (big3.empty())
                {
                    big3.push_back(a);
                    if (adj[0][a].size() == 3)for (int i : adj[0] [a]) big3.push_back(i);
                } else
                {
                    vector<int> n3;
                    for (int i : big3)
                    {
                        bool good = false;
                        if (adj[0][a].size() == 3)for (int j : adj[0] [a]) if (j == i) good = true;
                        if (i == a) good = true;
                        if (good) n3.push_back(i);
                    }
                    big3 = n3;
                }

            }
        }

        if (big3.size() <= X - 1 && !big3.empty())
        {
            for (int l = 1; l <= 3; l++)
            {
                if (big3.size() < l)
                {
                    bad2[l] = true;
                } else
                {
                    for (int i = 0; i < n; i++)
                    {
                        if (i == big3[l - 1]) continue;
                        for (int j : adj[0][i]) if (j != big3[l - 1])
                        {
                            adj[l][i].push_back(j);
                            join(l, i, j);
                        }
                    }
                }
            }
        }
    }


    if (!all && big3.size() == 0)
    {
        bad = true;
    }

}

int CountCritical() {
    if (all) return n;
    if (bad) return 0;

    if (!second) return big3.size();

    int res = 0;
    for (int i = 1; i<= 3; i++) res += !bad2[i];
    return res;
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:169:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  169 |                 if (big3.size() < l)
      |                     ~~~~~~~~~~~~^~~

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