oj.uz

Submission #596433

# Submission time Handle Problem Language Result Execution time Memory
596433 2022-07-14T18:25:03 Z ogibogi2004 Parachute rings (IOI12_rings) C++14
0 / 100
 2837 ms 182524 KB 
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> >hist;
void Link(int A,int B);
void Init(int _N);
struct vectorche
{
    int arr[4];
    int ptr=-1;
    void push_back(int val)
    {
        ptr++;
        arr[ptr]=val;
    }
    void clear()
    {
        ptr=-1;
    }
    bool find(int val)
    {
        for(int j=0;j<=ptr;j++)if(arr[j]==val)return true;
        return false;
    }
    int size()
    {
        return ptr+1;
    }
};
const int MAXN=1e6;
vectorche g_with_big[MAXN];
vectorche g_without_big[MAXN];
bool found_big=0;
bool ans0=0;
int big;
int where_cycle;
int par[MAXN];
int sz[MAXN];
set<int>with_sz[16];
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);
    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()==N;
}
void Init(int _N)
{
    N=_N;
    init();
    for(int i=0;i<16;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].push_back(B);
        g_without_big[B].push_back(A);
        g_with_big[A].push_back(B);
        g_with_big[B].push_back(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].push_back(B);
            g_without_big[B].push_back(A);
            g_with_big[A].push_back(B);
            g_with_big[B].push_back(A);
        }
        else
        {
            g_with_big[A].push_back(B);
            g_with_big[B].push_back(A);
        }
        with_sz[g_without_big[A].size()].insert(A);
        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;
    }
    else if(found_big)return 0;
    //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))
        {
            vector<int>common;
            for(int j=0;j<=g_without_big[a1].ptr;j++)
            {
                auto xd=g_without_big[a1].arr[j];
                if(g_without_big[a2].find(xd))
                {
                    common.push_back(xd);
                }
            }
            if(common.size()==1)
            {
                if(with_sz[0].size()+with_sz[1].size()/2==cnt_comp+1)
                {
                    return 1;
                }
            }
            if(common.size()==2)
            {
                if(with_sz[0].size()+with_sz[1].size()/2==cnt_comp)
                {
                    return 2;
                }
            }
            ans0=0;
            return 0;
        }
        int cnt_common=0;

        for(int j=0;j<=g_without_big[a1].ptr;j++)
        {
            auto xd=g_without_big[a1].arr[j];
            if(g_without_big[a2].find(xd))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))cnte++;
    if(g_without_big[a1].find(a3))cnte++;
    if(g_without_big[a2].find(a3))cnte++;
    if(cnte==3)return 3;
    if(cnte==2)return 1;
    ans0=1;
    return 0;

}

Compilation message

rings.cpp: In function 'bool check()':
rings.cpp:83:49: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |     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()==N;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
rings.cpp:83:138: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |     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()==N;
      |                                                                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:178:61: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  178 |         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:178:152: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  178 |         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:218:57: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  218 |                 if(with_sz[0].size()+with_sz[1].size()/2==cnt_comp+1)
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
rings.cpp:225:57: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  225 |                 if(with_sz[0].size()+with_sz[1].size()/2==cnt_comp)
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 48212 KB Output is correct
2 Correct 29 ms 48532 KB Output is correct
3 Correct 30 ms 48524 KB Output is correct
4 Correct 18 ms 48228 KB Output is correct
5 Correct 21 ms 48404 KB Output is correct
6 Correct 25 ms 48532 KB Output is correct
7 Correct 19 ms 48468 KB Output is correct
8 Correct 25 ms 48468 KB Output is correct
9 Incorrect 22 ms 48588 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1739 ms 76964 KB Output is correct
2 Runtime error 2837 ms 182524 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 48212 KB Output is correct
2 Correct 29 ms 48532 KB Output is correct
3 Correct 30 ms 48524 KB Output is correct
4 Correct 18 ms 48228 KB Output is correct
5 Correct 21 ms 48404 KB Output is correct
6 Correct 25 ms 48532 KB Output is correct
7 Correct 19 ms 48468 KB Output is correct
8 Correct 25 ms 48468 KB Output is correct
9 Incorrect 22 ms 48588 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 48212 KB Output is correct
2 Correct 29 ms 48532 KB Output is correct
3 Correct 30 ms 48524 KB Output is correct
4 Correct 18 ms 48228 KB Output is correct
5 Correct 21 ms 48404 KB Output is correct
6 Correct 25 ms 48532 KB Output is correct
7 Correct 19 ms 48468 KB Output is correct
8 Correct 25 ms 48468 KB Output is correct
9 Incorrect 22 ms 48588 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 48212 KB Output is correct
2 Correct 29 ms 48532 KB Output is correct
3 Correct 30 ms 48524 KB Output is correct
4 Correct 18 ms 48228 KB Output is correct
5 Correct 21 ms 48404 KB Output is correct
6 Correct 25 ms 48532 KB Output is correct
7 Correct 19 ms 48468 KB Output is correct
8 Correct 25 ms 48468 KB Output is correct
9 Incorrect 22 ms 48588 KB Output isn't correct
10 Halted 0 ms 0 KB -