2015年4月24日 星期五

2015/04/24 IOI 2012 Parachute Rings

// http://wcipeg.com/problems/desc/ioi1212
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

bool divide;
bool OK[4];
int bs[4];

int N, M;
int ring;

bool fine = true;

int cir; int now;
vector<int> v[2000000];
vector<int> e[2000000][4];

int par[2000000][5];
int sz[2000000];

int ask(int x, int i = 4)
{
    return x == par[x][i] ? x : par[x][i] = ask(par[x][i], i);
}

void merge(int x, int y, int i = 4)
{
    int px = ask(x, i);
    int py = ask(y, i);

    par[px][i] = py;
    if( px != py && i == 4 ) sz[py] += sz[px];
}

int main()
{
    scanf("%d %d", &N, &M);

    for(int Ni = 0; Ni < N; Ni++)
        for(int i = 0; i < 5; i++)
            par[Ni][i] = Ni, sz[Ni] = 1;

    now = N;

    for(int Mi = 0; Mi < M; Mi++)
    {
        int x;
        scanf("%d", &x);

        if( x == -1 )
        {
            if( !fine ) puts("0");
            else if( !divide ) printf("%d\n", now);
            else
            {
                int cnt = 0;
                for(int i = 0; i < 4; i++)
                    cnt += OK[i];
                printf("%d\n", cnt);
            }
        }
        else
        {
            int y;
            scanf("%d", &y);

            if( !divide )
            {
                v[x].push_back(y);
                v[y].push_back(x);

                int p = -1;

                if( v[x].size() == 3 ) p = x;
                else if( v[y].size() == 3 ) p = y;

                if( p != -1 )
                {
                    divide = true;

                    bs[3] = p;
                    for(int i = 0; i < 3; i++)
                        bs[i] = v[p][i];

                    for(int i = 0; i < 4; i++)
                        OK[i] = true;

                    for(int Ni = 0; Ni < N; Ni++)
                        for(int vi = 0; vi < v[Ni].size(); vi++)
                        {
                            int t = v[Ni][vi];

                            for(int i = 0; i < 4; i++)
                            {
                                if( bs[i] != Ni && bs[i] != t && Ni < t )
                                {
                                    e[Ni][i].push_back(t);
                                    e[t][i].push_back(Ni);

                                    if( ask(t, i) == ask(Ni, i) ) OK[i] = false;
                                    else merge(t, Ni, i);

                                    if( e[Ni][i].size() == 3 || e[t][i].size() == 3 )
                                        OK[i] = false;
                                }
                            }
                        }
                }
                else
                {
                    if( ask(x) == ask(y) ) cir++, now = sz[ask(x)];
                    if( cir == 2 ) fine = false;
                    merge(x, y);
                }
            }

            else
            {
                for(int i = 0; i < 4; i++)
                {
                    if( bs[i] != x && bs[i] != y )
                    {
                        e[x][i].push_back(y);
                        e[y][i].push_back(x);

                        if( ask(x, i) == ask(y, i) ) OK[i] = false;
                        else merge(x, y, i);

                        if( e[x][i].size() == 3 || e[y][i].size() == 3 )
                            OK[i] = false;
                    }
                }
            }
        }
    }
}

沒有留言:

張貼留言