제출 #596405

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
596405		ogibogi2004	낙하산 고리들 (IOI12_rings)	C++14	0 / 100	1895 ms	262144 KiB

rings

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> >hist;
void Link(int A,int B);
void Init(int _N);

const int MAXN=1e6+6;
set<int>g_with_big[MAXN];
set<int>g_without_big[MAXN];
bool found_big=0;
bool ans0=0;
int big;
set<pair<int,int> >nodes;
int where_cycle;
int par[MAXN];
int sz[MAXN];
set<int>with_sz[MAXN];
int cnt_comp=1;
int N;
bool cycle[MAXN];
void init()
{
    cnt_comp=N;
    for(int i=0;i<MAXN;i++)cycle[i]=0;
    for(int i=0;i<MAXN;i++)sz[i]=1;
    for(int i=0;i<MAXN;i++)par[i]=i;
}
void join(int p,int q)
{
    cnt_comp--;
    if(sz[p]>sz[q])
    {
        par[q]=p;
        sz[p]+=sz[q];
    }
    else
    {
        par[p]=q;
        sz[q]+=sz[p];
    }
}
int getRoot(int u)
{
    if(u==par[u])return u;
    return par[u]=getRoot(par[u]);
}
void rmv_big(int u)
{
    big=u;found_big=1;
    Init(N);
    cnt_comp--;
    for(int i=0;i<MAXN;i++)g_without_big[i].clear();
    for(int i=0;i<MAXN;i++)g_with_big[i].clear();
    for(auto xd:hist)
    {
        if(xd.first==u)continue;
        if(xd.second==u)continue;
        Link(xd.first,xd.second);
    }
}
bool check()
{
    return with_sz[1].size()/2+with_sz[0].size()==cnt_comp&&with_sz[1].size()%2==0&&with_sz[0].size()+with_sz[1].size()+with_sz[2].size()+found_big==N;
}
void Init(int _N)
{
    N=_N;
    init();
    for(int i=0;i<=N;i++)with_sz[i].clear();
    for(int i=0;i<N;i++)with_sz[0].insert(i);
}
void Link(int A, int B) {
    if(ans0)return;
    if(found_big==0)
    {
        with_sz[g_without_big[A].size()].erase(A);
        with_sz[g_without_big[B].size()].erase(B);
        g_without_big[A].insert(B);
        g_without_big[B].insert(A);
        g_with_big[A].insert(B);
        g_with_big[B].insert(A);
        with_sz[g_without_big[A].size()].insert(A);
        with_sz[g_without_big[B].size()].insert(B);
        if(g_without_big[A].size()>3&&g_without_big[B].size()>3)
        {
            ans0=1;
            return;
        }
        int a=getRoot(A),b=getRoot(B);
        if(a!=b)join(a,b);
        if(a==b)
        {
            cycle[a]=1;
            where_cycle=a;
        }
        if(g_without_big[A].size()>3)
        {
            rmv_big(A);
        }
        if(g_without_big[B].size()>3)
        {
            rmv_big(B);
        }
    }
    else
    {
        with_sz[g_without_big[A].size()].erase(A);
        with_sz[g_without_big[B].size()].erase(B);
        if(A!=big&&B!=big)
        {
            g_without_big[A].insert(B);
            g_without_big[B].insert(A);
            g_with_big[A].insert(B);
            g_with_big[B].insert(A);
        }
        else
        {
            g_with_big[A].insert(B);
            g_with_big[B].insert(A);
        }
        if(A!=big)with_sz[g_without_big[A].size()].insert(A);
        if(B!=big)with_sz[g_without_big[B].size()].insert(B);
        int a=getRoot(A),b=getRoot(B);
        if(a!=b&&A!=big&&B!=big)join(a,b);
        if(a==b)
        {
            cycle[a]=1;
            where_cycle=a;
        }
        if(g_without_big[A].size()>2&&A!=big)
        {
            ans0=1;
            return;
        }
        if(g_without_big[B].size()>2&&B!=big)
        {
            ans0=1;
            return;
        }
    }
    hist.push_back({A,B});
}

int CountCritical() {
    //cout<<"eho0\n";
    if(ans0)return 0;
    //cout<<"eho1\n";
    //cout<<with_sz[0].size()<<" "<<with_sz[1].size()<<" "<<with_sz[2].size()<<" "<<N<<" "<<cnt_comp<<" "<<found_big<<endl;
    if(check())
    {
        if(!found_big)return N;
        else return 1;
    }
    //cout<<"eho2\n";
    if(with_sz[3].size()==0)
    {
        if(!found_big&&with_sz[1].size()/2+with_sz[0].size()==cnt_comp-1&&with_sz[1].size()%2==0&&with_sz[0].size()+with_sz[1].size()+with_sz[2].size()==N)
        {
            //cout<<where_cycle<<endl;
            int t=getRoot(where_cycle);
            //cout<<t<<endl;
            //cout<<sz[t]<<endl;
            return sz[t];
        }
        ans0=1;
        return 0;
    }
    if(with_sz[3].size()>4)
    {
        ans0=1;
        return 0;
    }
    //cout<<"eho3\n";
    if(with_sz[3].size()==1)
    {
        int node=(*with_sz[3].begin());
        if(cycle[getRoot(node)])return 3;
        else return 4;
    }
    if(with_sz[3].size()==2)
    {
        auto it = with_sz[3].begin();
        int a1=(*it);it++;int a2=(*it);
        if(g_without_big[a1].find(a2)==g_without_big[a1].end())
        {
            ans0=0;
            return 0;
        }
        int cnt_common=0;
        for(auto xd:g_without_big[a1])
        {
            if(g_without_big[a2].find(xd)!=g_without_big[a2].end())cnt_common++;
        }
        if(cnt_common==0)
        {
            return 2;
        }
        if(cnt_common==1)return 3;
        return 2;
    }
    //cout<<"eho4\n";
    if(with_sz[3].size()==4)
    {
        ans0=1;return 0;
    }
    //cout<<"eho5\n";
    auto it = with_sz[3].begin();
    int a1=(*it);it++;
    int a2=(*it);it++;
    int a3=(*it);
    int cnte=0;
    if(g_without_big[a1].find(a2)!=g_without_big[a1].end())cnte++;
    if(g_without_big[a1].find(a3)!=g_without_big[a1].end())cnte++;
    if(g_without_big[a3].find(a2)!=g_without_big[a3].end())cnte++;
    if(cnte==3)return 3;
    if(cnte==2)return 1;
    ans0=1;
    return 0;

}

컴파일 시 표준 에러 (stderr) 메시지

rings.cpp: In function 'bool check()':
rings.cpp:63:49: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |     return with_sz[1].size()/2+with_sz[0].size()==cnt_comp&&with_sz[1].size()%2==0&&with_sz[0].size()+with_sz[1].size()+with_sz[2].size()+found_big==N;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
rings.cpp:63:148: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |     return with_sz[1].size()/2+with_sz[0].size()==cnt_comp&&with_sz[1].size()%2==0&&with_sz[0].size()+with_sz[1].size()+with_sz[2].size()+found_big==N;
      |                                                                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:157:61: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  157 |         if(!found_big&&with_sz[1].size()/2+with_sz[0].size()==cnt_comp-1&&with_sz[1].size()%2==0&&with_sz[0].size()+with_sz[1].size()+with_sz[2].size()==N)
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
rings.cpp:157:152: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  157 |         if(!found_big&&with_sz[1].size()/2+with_sz[0].size()==cnt_comp-1&&with_sz[1].size()%2==0&&with_sz[0].size()+with_sz[1].size()+with_sz[2].size()==N)
      |                                                                                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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