oj.uz

Submission #63419

# Submission time Handle Problem Language Result Execution time Memory
63419 2018-08-01T18:36:36 Z Vahan Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 86712 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -