oj.uz

Submission #350776

# Submission time Handle Problem Language Result Execution time Memory
350776 2021-01-19T08:18:34 Z juggernaut Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 26580 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],linker;
bool dfs(int v,int p){
    bool flag=false;
    vis[v]=true;
    for(int to:g[v])if(to!=p){
        if(on[to])continue;
        if(flag)return false;
        if(vis[to])return false;
        if(!dfs(to,v))return false;
        flag=true;
    }
    return true;
}
void dfs2(int v){
    linker++;
    vis[v]=1;
    for(int to:g[v])if(!vis[to])dfs2(to);
}
bool check(){
    for(int i=0;i<n;i++)vis[i]=0;
    for(int i=0;i<n;i++)if(!on[i]&&!vis[i]&&deg[i]<2)if(!dfs(i,i))return false;
    for(int i=0;i<n;i++)if(!vis[i]&&!on[i])return false;
    return true;
}
int mx=-1,cnt=0,global_ans;
void Init(int N){n=N;global_ans=n;}
int get_answer(){
    if(mx>=4){
        if(cnt!=1)return 0;
        cnt=0;
        for(int i=0;i<n;i++){
            if(deg[i]==mx){
                on[i]=true;
                for(auto to:g[i])deg[to]--;
                cnt+=check();
                for(auto to:g[i])deg[to]++;
                on[i]=false;
            }
        }
        return cnt;
    }else if(mx<2)return n;
    else if(mx==2){
        for(int i=0;i<n;i++)vis[i]=0;
        for(int i=0;i<n;i++)if(!vis[i]&&deg[i]<2)dfs(i,i);
        bool flag=false;
        for(int i=0;i<n;i++)if(!vis[i]){
            if(flag)return 0;
            linker=0;
            dfs2(i);
            flag=true;
        }
        if(flag)return linker;
        return n;
    }else if(mx==3){
        for(int i=0;i<n;i++){
            cnt=0;
            if(mx==deg[i]){
                on[i]=true;
                for(auto to:g[i])deg[to]--;
                cnt+=check();
                for(auto to:g[i])deg[to]++;
                on[i]=false;
                for(int to:g[i]){
                    on[to]=true;
                    for(auto to2:g[to])deg[to2]--;
                    cnt+=check();
                    for(auto to2:g[to])deg[to2]++;
                    on[to]=false;
                }
                return cnt;
            }
        }
    }
}
void Link(int x,int y){
    g[x].push_back(y);
    g[y].push_back(x);
    deg[x]++;
    deg[y]++;
    if(deg[x]>mx){
        mx=deg[x];
        cnt=1;
    }else if(deg[x]==mx)cnt++;
    if(deg[y]>mx){
        mx=deg[y];
        cnt=1;
    }else if(deg[y]==mx)cnt++;
    if(mx>4)return;
    global_ans=get_answer();
}
int CountCritical(){
    return global_ans;
}
/*
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 get_answer()':
rings.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
   81 | }
      | ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 690 ms 24300 KB Output is correct
3 Correct 53 ms 24172 KB Output is correct
4 Correct 33 ms 23916 KB Output is correct
5 Correct 157 ms 24044 KB Output is correct
6 Correct 439 ms 24216 KB Output is correct
7 Correct 45 ms 23916 KB Output is correct
8 Correct 270 ms 24300 KB Output is correct
9 Correct 1218 ms 24340 KB Output is correct
10 Correct 1454 ms 24224 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4014 ms 26580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 690 ms 24300 KB Output is correct
3 Correct 53 ms 24172 KB Output is correct
4 Correct 33 ms 23916 KB Output is correct
5 Correct 157 ms 24044 KB Output is correct
6 Correct 439 ms 24216 KB Output is correct
7 Correct 45 ms 23916 KB Output is correct
8 Correct 270 ms 24300 KB Output is correct
9 Correct 1218 ms 24340 KB Output is correct
10 Correct 1454 ms 24224 KB Output is correct
11 Correct 1194 ms 24212 KB Output is correct
12 Correct 1983 ms 24536 KB Output is correct
13 Correct 3891 ms 24344 KB Output is correct
14 Correct 21 ms 24044 KB Output is correct
15 Correct 21 ms 24172 KB Output is correct
16 Correct 1833 ms 24428 KB Output is correct
17 Correct 339 ms 24300 KB Output is correct
18 Correct 201 ms 24428 KB Output is correct
19 Correct 2178 ms 24292 KB Output is correct
20 Execution timed out 4037 ms 24556 KB Time limit exceeded

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 690 ms 24300 KB Output is correct
3 Correct 53 ms 24172 KB Output is correct
4 Correct 33 ms 23916 KB Output is correct
5 Correct 157 ms 24044 KB Output is correct
6 Correct 439 ms 24216 KB Output is correct
7 Correct 45 ms 23916 KB Output is correct
8 Correct 270 ms 24300 KB Output is correct
9 Correct 1218 ms 24340 KB Output is correct
10 Correct 1454 ms 24224 KB Output is correct
11 Correct 1194 ms 24212 KB Output is correct
12 Correct 1983 ms 24536 KB Output is correct
13 Correct 3891 ms 24344 KB Output is correct
14 Correct 21 ms 24044 KB Output is correct
15 Correct 21 ms 24172 KB Output is correct
16 Correct 1833 ms 24428 KB Output is correct
17 Correct 339 ms 24300 KB Output is correct
18 Correct 201 ms 24428 KB Output is correct
19 Correct 2178 ms 24292 KB Output is correct
20 Execution timed out 4037 ms 24556 KB Time limit exceeded

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 690 ms 24300 KB Output is correct
3 Correct 53 ms 24172 KB Output is correct
4 Correct 33 ms 23916 KB Output is correct
5 Correct 157 ms 24044 KB Output is correct
6 Correct 439 ms 24216 KB Output is correct
7 Correct 45 ms 23916 KB Output is correct
8 Correct 270 ms 24300 KB Output is correct
9 Correct 1218 ms 24340 KB Output is correct
10 Correct 1454 ms 24224 KB Output is correct
11 Execution timed out 4014 ms 26580 KB Time limit exceeded
12 Halted 0 ms 0 KB -