답안 #63419 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63419	2018-08-01T18:36:36 Z	Vahan	낙하산 고리들 (IOI12_rings)	C++17	55 / 100	4000 ms	86712 KB

rings

#include<vector>
#include<iostream>
using namespace std;
vector<int> g[2000000];
int n,u[2000000],q,p;
int sz[2000000],pa[2000000];
int CountCritical();
void crset(int a)
{
    sz[a]=1;
    pa[a]=a;
}
int getparent(int a)
{
    if(pa[a]==a)
        return a;
    pa[a]=getparent(pa[a]);
    return pa[a];
}
void setunion(int a,int b)
{
    a=getparent(a);
    b=getparent(b);
    if(a==b)
    {
        q++;
        p+=sz[a];
    }
    if(a>b)
    {
        sz[a]+=sz[b];
        pa[b]=a;
    }
    if(a<b)
    {
        sz[b]+=sz[a];
        pa[a]=b;
    }
}
void dfs(int v)
{
    u[v]=1;
    for(int j=0;j<g[v].size();j++)
    {
        int to=g[v][j];
        if(u[to]==0)
            dfs(to);
    }
}
int stug (int x)
{
    int mq=0;
    for(int i=0;i<n;i++)
    {
        if(i==x)
            continue;
        int qq=0;
        for(int j=0;j<g[i].size();j++)
        {
            int to= g[i][j];
            if(to==x)
                continue;
            qq++;
        }
        if(qq==3)
            return 0;
        if(qq==0)
            mq+=2;
        if(qq==1)
            mq+=1;
    }
    for(int i=0;i<n;i++)
        u[i]=0;
    u[x]=1;
    int xq=0;
    for(int i=0;i<n;i++)
    {
        if(u[i]==0)
        {
            dfs(i);
            xq++;
        }
    }
    if(2*xq==mq)
        return 1;
    else
        return 0;
}
void Init(int N_) {

  n = N_;

}

void Link(int A, int B) {
    g[A].push_back(B);
    g[B].push_back(A);
}

int CountCritical() {
    for(int i=0;i<n;i++)
    {
        if(g[i].size()>=4)
        {
            if(stug(i))
                return 1;
            else
                return 0;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(g[i].size()==3)
        {
            p=0;
            if(stug(i))
                p++;
            for(int j=0;j<g[i].size();j++)
            {
                int to=g[i][j];
                if(stug(to))
                    p++;
            }
            return p;
        }
    }
    p=0;
    q=0;
    for(int i=0;i<n;i++)
        crset(i);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<g[i].size();j++)
        {
            int to=g[i][j];
            if(to>i)
                setunion(i,to);
        }
    }
    if(q==1)
        return p;
    if(q>1)
        return 0;
    if(q==0)
        return n;
}

Compilation message

rings.cpp: In function 'void dfs(int)':
rings.cpp:43:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<g[v].size();j++)
                 ~^~~~~~~~~~~~
rings.cpp: In function 'int stug(int)':
rings.cpp:58:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<g[i].size();j++)
                     ~^~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:118:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<g[i].size();j++)
                         ~^~~~~~~~~~~~
rings.cpp:133:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<g[i].size();j++)
                     ~^~~~~~~~~~~~
rings.cpp:146:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	47352 KB	Output is correct
2	Correct	43 ms	47604 KB	Output is correct
3	Correct	45 ms	47680 KB	Output is correct
4	Correct	43 ms	47680 KB	Output is correct
5	Correct	43 ms	47680 KB	Output is correct
6	Correct	44 ms	47680 KB	Output is correct
7	Correct	43 ms	47680 KB	Output is correct
8	Correct	43 ms	47680 KB	Output is correct
9	Correct	44 ms	47704 KB	Output is correct
10	Correct	43 ms	47764 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	451 ms	68052 KB	Output is correct
2	Correct	997 ms	75936 KB	Output is correct
3	Correct	905 ms	75936 KB	Output is correct
4	Correct	1120 ms	86660 KB	Output is correct
5	Correct	1133 ms	86712 KB	Output is correct
6	Correct	1132 ms	86712 KB	Output is correct
7	Correct	886 ms	86712 KB	Output is correct
8	Correct	1613 ms	86712 KB	Output is correct
9	Correct	1463 ms	86712 KB	Output is correct
10	Correct	856 ms	86712 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	47352 KB	Output is correct
2	Correct	43 ms	47604 KB	Output is correct
3	Correct	45 ms	47680 KB	Output is correct
4	Correct	43 ms	47680 KB	Output is correct
5	Correct	43 ms	47680 KB	Output is correct
6	Correct	44 ms	47680 KB	Output is correct
7	Correct	43 ms	47680 KB	Output is correct
8	Correct	43 ms	47680 KB	Output is correct
9	Correct	44 ms	47704 KB	Output is correct
10	Correct	43 ms	47764 KB	Output is correct
11	Correct	60 ms	86712 KB	Output is correct
12	Correct	74 ms	86712 KB	Output is correct
13	Correct	108 ms	86712 KB	Output is correct
14	Correct	67 ms	86712 KB	Output is correct
15	Correct	72 ms	86712 KB	Output is correct
16	Correct	69 ms	86712 KB	Output is correct
17	Correct	51 ms	86712 KB	Output is correct
18	Correct	49 ms	86712 KB	Output is correct
19	Correct	71 ms	86712 KB	Output is correct
20	Correct	94 ms	86712 KB	Output is correct

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	47352 KB	Output is correct
2	Correct	43 ms	47604 KB	Output is correct
3	Correct	45 ms	47680 KB	Output is correct
4	Correct	43 ms	47680 KB	Output is correct
5	Correct	43 ms	47680 KB	Output is correct
6	Correct	44 ms	47680 KB	Output is correct
7	Correct	43 ms	47680 KB	Output is correct
8	Correct	43 ms	47680 KB	Output is correct
9	Correct	44 ms	47704 KB	Output is correct
10	Correct	43 ms	47764 KB	Output is correct
11	Correct	60 ms	86712 KB	Output is correct
12	Correct	74 ms	86712 KB	Output is correct
13	Correct	108 ms	86712 KB	Output is correct
14	Correct	67 ms	86712 KB	Output is correct
15	Correct	72 ms	86712 KB	Output is correct
16	Correct	69 ms	86712 KB	Output is correct
17	Correct	51 ms	86712 KB	Output is correct
18	Correct	49 ms	86712 KB	Output is correct
19	Correct	71 ms	86712 KB	Output is correct
20	Correct	94 ms	86712 KB	Output is correct
21	Execution timed out	4043 ms	86712 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	47352 KB	Output is correct
2	Correct	43 ms	47604 KB	Output is correct
3	Correct	45 ms	47680 KB	Output is correct
4	Correct	43 ms	47680 KB	Output is correct
5	Correct	43 ms	47680 KB	Output is correct
6	Correct	44 ms	47680 KB	Output is correct
7	Correct	43 ms	47680 KB	Output is correct
8	Correct	43 ms	47680 KB	Output is correct
9	Correct	44 ms	47704 KB	Output is correct
10	Correct	43 ms	47764 KB	Output is correct
11	Correct	451 ms	68052 KB	Output is correct
12	Correct	997 ms	75936 KB	Output is correct
13	Correct	905 ms	75936 KB	Output is correct
14	Correct	1120 ms	86660 KB	Output is correct
15	Correct	1133 ms	86712 KB	Output is correct
16	Correct	1132 ms	86712 KB	Output is correct
17	Correct	886 ms	86712 KB	Output is correct
18	Correct	1613 ms	86712 KB	Output is correct
19	Correct	1463 ms	86712 KB	Output is correct
20	Correct	856 ms	86712 KB	Output is correct
21	Correct	60 ms	86712 KB	Output is correct
22	Correct	74 ms	86712 KB	Output is correct
23	Correct	108 ms	86712 KB	Output is correct
24	Correct	67 ms	86712 KB	Output is correct
25	Correct	72 ms	86712 KB	Output is correct
26	Correct	69 ms	86712 KB	Output is correct
27	Correct	51 ms	86712 KB	Output is correct
28	Correct	49 ms	86712 KB	Output is correct
29	Correct	71 ms	86712 KB	Output is correct
30	Correct	94 ms	86712 KB	Output is correct
31	Execution timed out	4043 ms	86712 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

답안 #63419

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 0 / 14.0

Subtask #5 0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
0 / 14.0

Subtask #5
0 / 31.0