oj.uz

답안 #18799

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18799 2016-02-15T13:05:38 Z ggoh 낙하산 고리들 (IOI12_rings) C++
0 / 100
 2025 ms 70592 KB 
#include<cstdio>
#include<algorithm>

int a,cyc,t,co[8],link[1000003][2],par[8][1000002],deg[8][1000002],cycsz,sz[1000002],rank[8][1000002];
bool overtwo,check[8];
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];}
    else
    {
        if(rank[num][AA]==rank[num][BB])rank[num][AA]++;
        par[num][BB]=AA;
        if(num==0)sz[AA]+=sz[BB];
    }
}
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 o)
{
    int u=1;
    co[u++]=o;
    for(int i=0;i<t;i++)
    {
        if(link[i][0]==o)co[u++]=link[i][1];
        if(link[i][1]==o)co[u++]=link[i][0];
    }
    for(int i=1;i<=4;i++)
    {
        check[i]=1;
        for(int j=1;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=1;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+1;q=B+1;
    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==0)
    {
        if(cyc==1)return cycsz;
        else return a;
    }
    else
    {
        int ans=0;
        for(int i=1;i<=4;i++)ans+=check[i];
        return ans;
    }
    
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 12800 KB Output is correct
2 Correct 1722 ms 56952 KB Output is correct
3 Correct 1846 ms 70592 KB Output is correct
4 Correct 694 ms 70592 KB Output is correct
5 Correct 699 ms 70592 KB Output is correct
6 Correct 685 ms 70592 KB Output is correct
7 Correct 1781 ms 70592 KB Output is correct
8 Incorrect 2025 ms 70592 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 884 KB Output is correct
3 Correct 4 ms 952 KB Output is correct
4 Correct 2 ms 952 KB Output is correct
5 Correct 3 ms 952 KB Output is correct
6 Correct 3 ms 952 KB Output is correct
7 Correct 2 ms 952 KB Output is correct
8 Correct 4 ms 952 KB Output is correct
9 Incorrect 4 ms 992 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 884 KB Output is correct
3 Correct 4 ms 952 KB Output is correct
4 Correct 2 ms 952 KB Output is correct
5 Correct 3 ms 952 KB Output is correct
6 Correct 3 ms 952 KB Output is correct
7 Correct 2 ms 952 KB Output is correct
8 Correct 4 ms 952 KB Output is correct
9 Incorrect 4 ms 992 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 884 KB Output is correct
3 Correct 4 ms 952 KB Output is correct
4 Correct 2 ms 952 KB Output is correct
5 Correct 3 ms 952 KB Output is correct
6 Correct 3 ms 952 KB Output is correct
7 Correct 2 ms 952 KB Output is correct
8 Correct 4 ms 952 KB Output is correct
9 Incorrect 4 ms 992 KB Output isn't correct
10 Halted 0 ms 0 KB -