oj.uz

Submission #596417

# Submission time Handle Problem Language Result Execution time Memory
596417 2022-07-14T17:48:35 Z ogibogi2004 Parachute rings (IOI12_rings) C++14
20 / 100
 1953 ms 262144 KB 
#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);
    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<=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);
        }
        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)==g_without_big[a1].end())
        {
            vector<int>common;
            for(auto xd:g_without_big[a1])
            {
                if(g_without_big[a2].find(xd)!=g_without_big[a2].end())
                {
                    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(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;

}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 149984 KB Output is correct
2 Correct 99 ms 150928 KB Output is correct
3 Correct 94 ms 151168 KB Output is correct
4 Correct 65 ms 150124 KB Output is correct
5 Correct 69 ms 150700 KB Output is correct
6 Correct 73 ms 151124 KB Output is correct
7 Correct 68 ms 150312 KB Output is correct
8 Correct 69 ms 150968 KB Output is correct
9 Correct 74 ms 151240 KB Output is correct
10 Correct 73 ms 151116 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1953 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 149984 KB Output is correct
2 Correct 99 ms 150928 KB Output is correct
3 Correct 94 ms 151168 KB Output is correct
4 Correct 65 ms 150124 KB Output is correct
5 Correct 69 ms 150700 KB Output is correct
6 Correct 73 ms 151124 KB Output is correct
7 Correct 68 ms 150312 KB Output is correct
8 Correct 69 ms 150968 KB Output is correct
9 Correct 74 ms 151240 KB Output is correct
10 Correct 73 ms 151116 KB Output is correct
11 Incorrect 77 ms 151280 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 149984 KB Output is correct
2 Correct 99 ms 150928 KB Output is correct
3 Correct 94 ms 151168 KB Output is correct
4 Correct 65 ms 150124 KB Output is correct
5 Correct 69 ms 150700 KB Output is correct
6 Correct 73 ms 151124 KB Output is correct
7 Correct 68 ms 150312 KB Output is correct
8 Correct 69 ms 150968 KB Output is correct
9 Correct 74 ms 151240 KB Output is correct
10 Correct 73 ms 151116 KB Output is correct
11 Incorrect 77 ms 151280 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 149984 KB Output is correct
2 Correct 99 ms 150928 KB Output is correct
3 Correct 94 ms 151168 KB Output is correct
4 Correct 65 ms 150124 KB Output is correct
5 Correct 69 ms 150700 KB Output is correct
6 Correct 73 ms 151124 KB Output is correct
7 Correct 68 ms 150312 KB Output is correct
8 Correct 69 ms 150968 KB Output is correct
9 Correct 74 ms 151240 KB Output is correct
10 Correct 73 ms 151116 KB Output is correct
11 Runtime error 1953 ms 262144 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -