oj.uz

Submission #254657

# Submission time Handle Problem Language Result Execution time Memory
254657 2020-07-30T12:05:34 Z MKopchev Parachute rings (IOI12_rings) C++14
0 / 100
 1405 ms 104912 KB 
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e6+42;

int n;

int deg[10][nmax];

int ret;

vector< int > adj[nmax];

int parent[10][nmax];
int SZ[nmax];

void Init(int N)
{
    n=N;

    ret=n;

    for(int i=0;i<n;i++)
    {
        parent[0][i]=i;
        SZ[i]=1;
    }
}

set<int> big;

bool forced_small_group=0;

int root(int id,int node)
{
    if(parent[id][node]==node)return parent[id][node];
    parent[id][node]=root(id,parent[id][node]);
    return parent[id][node];
}

bool cycle;

vector< pair<int,int> > edges;

set<int> nums;

int ordered[10],pointer=0;
bool valid[10];

void small_group(int A,int B)
{
    //cout<<"small group "<<A<<" "<<B<<endl;

    for(int i=1;i<=pointer;i++)
        if(valid[i]&&A!=ordered[i]&&B!=ordered[i])
        {
            deg[i][A]++;
            deg[i][B]++;

            if(root(i,A)==root(i,B)||deg[i][A]>=3||deg[i][B]>=3)
            {
                valid[i]=0;
                ret--;
                continue;
            }

            parent[i][root(i,A)]=root(i,B);
        }

    //for(int i=1;i<=pointer;i++)cout<<ordered[i]<<" "<<valid[i]<<endl;
}
void create_small()
{
    for(auto k:big)
    {
        nums.insert(k);
        for(auto p:adj[k])
            nums.insert(p);
    }

    ret=0;
    for(auto k:nums)
    {
        pointer++;
        ordered[pointer]=k;
        valid[pointer]=1;
        ret++;

        for(int j=0;j<n;j++)
            parent[pointer][j]=j;

        //cout<<"k= "<<k<<endl;
    }

    for(auto k:edges)
        small_group(k.first,k.second);
}

void Link(int A, int B)
{
    edges.push_back({A,B});

    adj[A].push_back(B);
    adj[B].push_back(A);

    if(ret==0)return;

    if(forced_small_group)
    {
        small_group(A,B);
        return;
    }

    deg[0][A]++;
    deg[0][B]++;

    if(deg[0][A]>=3)big.insert(A);
    if(deg[0][B]>=3)big.insert(B);

    if(big.size()>=1)
    {
        forced_small_group=1;
        create_small();
        return;
    }

    if(root(0,A)!=root(0,B))
    {
        parent[0][root(0,A)]=root(0,B);
        SZ[root(0,B)]+=SZ[root(0,A)];
        return;
    }

    //a cycle with no degrees >=3
    if(cycle)
    {
        ret=0;
        return;
    }

    cycle=1;
    ret=SZ[root(0,A)];
}
int CountCritical()
{
    return ret;
}
/*
int main()
{
    Init(7);
    cout<<CountCritical()<<endl;//7
    Link(1, 2);
    cout<<CountCritical()<<endl;//7
    Link(0, 5);
    cout<<CountCritical()<<endl;//7
    Link(2, 0);
    cout<<CountCritical()<<endl;//7
    Link(3, 2);
    cout<<CountCritical()<<endl;//4
    Link(3, 5);
    cout<<CountCritical()<<endl;//3
    Link(4, 3);
    cout<<CountCritical()<<endl;//2
    return 0;
}
*/

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 16 ms 24320 KB Output is correct
3 Correct 17 ms 24448 KB Output is correct
4 Incorrect 14 ms 23944 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 55132 KB Output is correct
2 Correct 1048 ms 95824 KB Output is correct
3 Correct 890 ms 104912 KB Output is correct
4 Incorrect 1405 ms 78224 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 16 ms 24320 KB Output is correct
3 Correct 17 ms 24448 KB Output is correct
4 Incorrect 14 ms 23944 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 16 ms 24320 KB Output is correct
3 Correct 17 ms 24448 KB Output is correct
4 Incorrect 14 ms 23944 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 16 ms 24320 KB Output is correct
3 Correct 17 ms 24448 KB Output is correct
4 Incorrect 14 ms 23944 KB Output isn't correct
5 Halted 0 ms 0 KB -