oj.uz

Submission #18794

# Submission time Handle Problem Language Result Execution time Memory
18794 2016-02-15T12:42:02 Z ggoh Parachute rings (IOI12_rings) C++
0 / 100
 2001 ms 70688 KB 
#include<cstdio>
#include<algorithm>

int a,cyc,t,co[5],link[1000003][2],par[5][1000002],deg[5][1000002],cycsz,sz[1000002],rank[5][1000002];
bool overtwo,check[5];
int find(int num,int AA){if(AA==par[num][AA])return AA;else return par[num][AA]=find(num,par[num][AA]);}
void unite(int num,int AA,int BB)
{
    AA=find(num,AA);BB=find(num,BB);
    if(rank[num][AA]<rank[num][BB])par[num][AA]=BB;
    else
    {
        if(rank[num][AA]==rank[num][BB])rank[num][AA]++;
        par[num][BB]=AA;
    }
}
void add(int r,int s)
{
    for(int i=1;i<=4;i++)
    {
        if(co[i]==r||co[i]==s)continue;
        deg[i][r]++;deg[i][s]++;
        if(deg[i][r]>=3||deg[i][s]>=3)check[i]=0;
        r=find(i,r);s=find(i,s);
        if(r==s)check[i]=0;
        unite(i,r,s);
    }
}
void make(int r)
{
    int u=1;
    co[u++]=r;
    for(int i=0;i<t;i++)
    {
        if(link[i][0]==r)co[u++]=link[i][1];
        else if(link[i][1]==r)co[u++]=link[i][0];
    }
    for(int i=1;i<=4;i++)
    {
        check[i]=1;
        for(int j=0;j<a;j++)par[i][j]=j,rank[i][j]=1;
    }
    for(int i=0;i<t;i++)add(link[i][0],link[i][1]);
}
void Init(int N)
{
    a=N;
    for(int i=0;i<N;i++)rank[0][i]=1,par[0][i]=i,sz[i]=1;
}
void Link(int A, int B)
{
    int p,q;
    p=A;q=B;
    link[t][0]=p;link[t][1]=q;t++;
    deg[0][p]++;deg[0][q]++;
    if(deg[0][p]==3&&overtwo==0){
        overtwo=1;
        make(p);
    }
    else if(overtwo==0&&deg[0][q]==3)
    {
        overtwo=1;
        make(q);
    }
    else if(overtwo==0)
    {
        p=find(0,p);q=find(0,q);
        if(p==q){cyc++;cycsz=sz[p];}
        else
        {
            unite(0,p,q);
            sz[p]+=sz[q];
            sz[q]=sz[p];
        }
    }
    else
    {
        add(p,q);
    }
}
int CountCritical()
{
    if(cyc>1)return 0;
    if(overtwo)
    {
        int ans=0;
        for(int i=1;i<=4;i++)ans+=check[i];
        return ans;
    }
    else
    {
        if(cyc)return cycsz;
        else return a;
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 888 KB Output is correct
3 Correct 4 ms 1088 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 3 ms 1088 KB Output is correct
6 Correct 3 ms 1088 KB Output is correct
7 Correct 2 ms 1088 KB Output is correct
8 Correct 3 ms 1088 KB Output is correct
9 Incorrect 4 ms 1088 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 12748 KB Output is correct
2 Correct 1599 ms 57296 KB Output is correct
3 Correct 1607 ms 70688 KB Output is correct
4 Correct 690 ms 70688 KB Output is correct
5 Correct 711 ms 70688 KB Output is correct
6 Correct 658 ms 70688 KB Output is correct
7 Correct 1655 ms 70688 KB Output is correct
8 Incorrect 2001 ms 70688 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 888 KB Output is correct
3 Correct 4 ms 1088 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 3 ms 1088 KB Output is correct
6 Correct 3 ms 1088 KB Output is correct
7 Correct 2 ms 1088 KB Output is correct
8 Correct 3 ms 1088 KB Output is correct
9 Incorrect 4 ms 1088 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 888 KB Output is correct
3 Correct 4 ms 1088 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 3 ms 1088 KB Output is correct
6 Correct 3 ms 1088 KB Output is correct
7 Correct 2 ms 1088 KB Output is correct
8 Correct 3 ms 1088 KB Output is correct
9 Incorrect 4 ms 1088 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 888 KB Output is correct
3 Correct 4 ms 1088 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 3 ms 1088 KB Output is correct
6 Correct 3 ms 1088 KB Output is correct
7 Correct 2 ms 1088 KB Output is correct
8 Correct 3 ms 1088 KB Output is correct
9 Incorrect 4 ms 1088 KB Output isn't correct
10 Halted 0 ms 0 KB -