oj.uz

Submission #350951

# Submission time Handle Problem Language Result Execution time Memory
350951 2021-01-19T10:11:22 Z juggernaut Parachute rings (IOI12_rings) C++14
55 / 100
 4000 ms 82060 KB 
#ifndef EVAL
#include"grader.cpp"
#endif
#include<bits/stdc++.h>
using namespace std;
vector<int>g[1000005];
bool on[1000005],vis[1000005];
int n,deg[1000005];
int counter[5];
bool flag;
int cycle_size,cycle_number,cur_sz;
void update_counter(int x,int y){
    counter[min(x,4)]+=y;
}
#define DEBUG(x) cout<<#x<<"="<<x<<"\n"
void go(int v,int p){
    if(on[v])return;
    cur_sz++;
    vis[v]=1;
    for(int to:g[v])if(to!=p){
        if(vis[to]){
            flag=true;
            continue;
        }
        go(to,v);
    }
}
bool check(){
    for(int i=0;i<n;i++)vis[i]=0;
    for(int i=0;i<n;i++){
        if(on[i])continue;
        if(deg[i]>2)return false;
        if(vis[i])continue;
        flag=false;
        go(i,i);
        if(flag)return false;
    }
    return true;
}
void Init(int N){
    n=N;
    counter[0]=n;
}
void Link(int x,int y){
    g[x].push_back(y);
    g[y].push_back(x);
    update_counter(deg[x],-1);
    update_counter(deg[y],-1);
    deg[x]++;
    deg[y]++;
    update_counter(deg[x],+1);
    update_counter(deg[y],+1);
}
int CountCritical(){
    if(counter[4]){
        if(counter[4]!=1)return 0;
        for(int i=0;i<n;i++)
            if(deg[i]>3){
                on[i]=true;
                for(int to:g[i])deg[i]--,deg[to]--;
                int ans=check();
                for(int to:g[i])deg[i]++,deg[to]++;
                on[i]=false;
                return ans;
            }
    }else if(counter[3]){
        for(int i=0;i<n;i++)
            if(deg[i]>2){
                int ans=0;
                on[i]=true;
                for(int to:g[i])deg[i]--,deg[to]--;
                ans+=check();
                for(int to:g[i])deg[i]++,deg[to]++;
                on[i]=false;
                for(int to:g[i]){
                    on[to]=true;
                    for(int to2:g[to])deg[to]--,deg[to2]--;
                    ans+=check();
                    for(int to2:g[to])deg[to]++,deg[to2]++;
                    on[to]=false;
                }
                return ans;
            }
    }else{
        for(int i=0;i<n;i++)vis[i]=0;
        cycle_number=cycle_size=0;
        for(int i=0;i<n;i++){
            if(vis[i])continue;
            flag=false;
            cur_sz=0;
            go(i,i);
            if(flag)cycle_number++,cycle_size=cur_sz;
        }
        if(cycle_number==0)return n;
        else if(cycle_number==1)return cycle_size;
        else return 0;
    }
}
/*
7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1

*/

Compilation message

rings.cpp: In function 'int CountCritical()':
rings.cpp:98:1: warning: control reaches end of non-void function [-Wreturn-type]
   98 | }
      | ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 17 ms 24044 KB Output is correct
3 Correct 17 ms 24044 KB Output is correct
4 Correct 15 ms 23916 KB Output is correct
5 Correct 16 ms 24044 KB Output is correct
6 Correct 17 ms 24172 KB Output is correct
7 Correct 15 ms 23916 KB Output is correct
8 Correct 17 ms 24044 KB Output is correct
9 Correct 18 ms 24044 KB Output is correct
10 Correct 18 ms 24044 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 42860 KB Output is correct
2 Correct 1078 ms 53228 KB Output is correct
3 Correct 974 ms 55124 KB Output is correct
4 Correct 1271 ms 60524 KB Output is correct
5 Correct 1331 ms 61060 KB Output is correct
6 Correct 1268 ms 82060 KB Output is correct
7 Correct 921 ms 54616 KB Output is correct
8 Correct 2029 ms 58180 KB Output is correct
9 Correct 2048 ms 60784 KB Output is correct
10 Correct 957 ms 62060 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 17 ms 24044 KB Output is correct
3 Correct 17 ms 24044 KB Output is correct
4 Correct 15 ms 23916 KB Output is correct
5 Correct 16 ms 24044 KB Output is correct
6 Correct 17 ms 24172 KB Output is correct
7 Correct 15 ms 23916 KB Output is correct
8 Correct 17 ms 24044 KB Output is correct
9 Correct 18 ms 24044 KB Output is correct
10 Correct 18 ms 24044 KB Output is correct
11 Correct 29 ms 24044 KB Output is correct
12 Correct 48 ms 24300 KB Output is correct
13 Correct 58 ms 24300 KB Output is correct
14 Correct 32 ms 24044 KB Output is correct
15 Correct 42 ms 24044 KB Output is correct
16 Correct 38 ms 24428 KB Output is correct
17 Correct 24 ms 24300 KB Output is correct
18 Correct 26 ms 24556 KB Output is correct
19 Correct 39 ms 24300 KB Output is correct
20 Correct 84 ms 24300 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 17 ms 24044 KB Output is correct
3 Correct 17 ms 24044 KB Output is correct
4 Correct 15 ms 23916 KB Output is correct
5 Correct 16 ms 24044 KB Output is correct
6 Correct 17 ms 24172 KB Output is correct
7 Correct 15 ms 23916 KB Output is correct
8 Correct 17 ms 24044 KB Output is correct
9 Correct 18 ms 24044 KB Output is correct
10 Correct 18 ms 24044 KB Output is correct
11 Correct 29 ms 24044 KB Output is correct
12 Correct 48 ms 24300 KB Output is correct
13 Correct 58 ms 24300 KB Output is correct
14 Correct 32 ms 24044 KB Output is correct
15 Correct 42 ms 24044 KB Output is correct
16 Correct 38 ms 24428 KB Output is correct
17 Correct 24 ms 24300 KB Output is correct
18 Correct 26 ms 24556 KB Output is correct
19 Correct 39 ms 24300 KB Output is correct
20 Correct 84 ms 24300 KB Output is correct
21 Execution timed out 4051 ms 24752 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 17 ms 24044 KB Output is correct
3 Correct 17 ms 24044 KB Output is correct
4 Correct 15 ms 23916 KB Output is correct
5 Correct 16 ms 24044 KB Output is correct
6 Correct 17 ms 24172 KB Output is correct
7 Correct 15 ms 23916 KB Output is correct
8 Correct 17 ms 24044 KB Output is correct
9 Correct 18 ms 24044 KB Output is correct
10 Correct 18 ms 24044 KB Output is correct
11 Correct 557 ms 42860 KB Output is correct
12 Correct 1078 ms 53228 KB Output is correct
13 Correct 974 ms 55124 KB Output is correct
14 Correct 1271 ms 60524 KB Output is correct
15 Correct 1331 ms 61060 KB Output is correct
16 Correct 1268 ms 82060 KB Output is correct
17 Correct 921 ms 54616 KB Output is correct
18 Correct 2029 ms 58180 KB Output is correct
19 Correct 2048 ms 60784 KB Output is correct
20 Correct 957 ms 62060 KB Output is correct
21 Correct 29 ms 24044 KB Output is correct
22 Correct 48 ms 24300 KB Output is correct
23 Correct 58 ms 24300 KB Output is correct
24 Correct 32 ms 24044 KB Output is correct
25 Correct 42 ms 24044 KB Output is correct
26 Correct 38 ms 24428 KB Output is correct
27 Correct 24 ms 24300 KB Output is correct
28 Correct 26 ms 24556 KB Output is correct
29 Correct 39 ms 24300 KB Output is correct
30 Correct 84 ms 24300 KB Output is correct
31 Execution timed out 4051 ms 24752 KB Time limit exceeded
32 Halted 0 ms 0 KB -