oj.uz

답안 #18797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18797 2016-02-15T12:57:30 Z ggoh 낙하산 고리들 (IOI12_rings) C++
0 / 100
 1978 ms 70700 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;if(num==0)sz[BB]+=sz[AA],sz[AA]=0;}
    else
    {
        if(rank[num][AA]==rank[num][BB])rank[num][AA]++;
        par[num][BB]=AA;
        if(num==0)sz[AA]+=sz[BB],sz[BB]=0;
    }
}
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];
        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<a;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);
        }
    }
    else
    {
        add(p,q);
    }
}
int CountCritical()
{
    if(cyc>1)return 0;
    else 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Correct 4 ms 904 KB Output is correct
4 Correct 2 ms 904 KB Output is correct
5 Correct 2 ms 904 KB Output is correct
6 Correct 3 ms 904 KB Output is correct
7 Correct 2 ms 916 KB Output is correct
8 Correct 3 ms 916 KB Output is correct
9 Incorrect 4 ms 1044 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 12736 KB Output is correct
2 Correct 1552 ms 57160 KB Output is correct
3 Correct 1591 ms 70700 KB Output is correct
4 Correct 673 ms 70700 KB Output is correct
5 Correct 642 ms 70700 KB Output is correct
6 Correct 635 ms 70700 KB Output is correct
7 Correct 1521 ms 70700 KB Output is correct
8 Incorrect 1978 ms 70700 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Correct 4 ms 904 KB Output is correct
4 Correct 2 ms 904 KB Output is correct
5 Correct 2 ms 904 KB Output is correct
6 Correct 3 ms 904 KB Output is correct
7 Correct 2 ms 916 KB Output is correct
8 Correct 3 ms 916 KB Output is correct
9 Incorrect 4 ms 1044 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Correct 4 ms 904 KB Output is correct
4 Correct 2 ms 904 KB Output is correct
5 Correct 2 ms 904 KB Output is correct
6 Correct 3 ms 904 KB Output is correct
7 Correct 2 ms 916 KB Output is correct
8 Correct 3 ms 916 KB Output is correct
9 Incorrect 4 ms 1044 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Correct 4 ms 904 KB Output is correct
4 Correct 2 ms 904 KB Output is correct
5 Correct 2 ms 904 KB Output is correct
6 Correct 3 ms 904 KB Output is correct
7 Correct 2 ms 916 KB Output is correct
8 Correct 3 ms 916 KB Output is correct
9 Incorrect 4 ms 1044 KB Output isn't correct
10 Halted 0 ms 0 KB -