oj.uz

Submission #350784

# Submission time Handle Problem Language Result Execution time Memory
350784 2021-01-19T08:23:31 Z juggernaut Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 26604 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;
        int 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++){
            int 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 642 ms 24172 KB Output is correct
3 Correct 64 ms 24044 KB Output is correct
4 Correct 29 ms 23916 KB Output is correct
5 Correct 151 ms 24172 KB Output is correct
6 Correct 465 ms 24428 KB Output is correct
7 Correct 37 ms 24064 KB Output is correct
8 Correct 244 ms 24044 KB Output is correct
9 Correct 1228 ms 24384 KB Output is correct
10 Correct 1237 ms 24256 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4072 ms 26604 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 642 ms 24172 KB Output is correct
3 Correct 64 ms 24044 KB Output is correct
4 Correct 29 ms 23916 KB Output is correct
5 Correct 151 ms 24172 KB Output is correct
6 Correct 465 ms 24428 KB Output is correct
7 Correct 37 ms 24064 KB Output is correct
8 Correct 244 ms 24044 KB Output is correct
9 Correct 1228 ms 24384 KB Output is correct
10 Correct 1237 ms 24256 KB Output is correct
11 Correct 1174 ms 24308 KB Output is correct
12 Correct 1950 ms 24356 KB Output is correct
13 Execution timed out 4001 ms 24608 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 642 ms 24172 KB Output is correct
3 Correct 64 ms 24044 KB Output is correct
4 Correct 29 ms 23916 KB Output is correct
5 Correct 151 ms 24172 KB Output is correct
6 Correct 465 ms 24428 KB Output is correct
7 Correct 37 ms 24064 KB Output is correct
8 Correct 244 ms 24044 KB Output is correct
9 Correct 1228 ms 24384 KB Output is correct
10 Correct 1237 ms 24256 KB Output is correct
11 Correct 1174 ms 24308 KB Output is correct
12 Correct 1950 ms 24356 KB Output is correct
13 Execution timed out 4001 ms 24608 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 642 ms 24172 KB Output is correct
3 Correct 64 ms 24044 KB Output is correct
4 Correct 29 ms 23916 KB Output is correct
5 Correct 151 ms 24172 KB Output is correct
6 Correct 465 ms 24428 KB Output is correct
7 Correct 37 ms 24064 KB Output is correct
8 Correct 244 ms 24044 KB Output is correct
9 Correct 1228 ms 24384 KB Output is correct
10 Correct 1237 ms 24256 KB Output is correct
11 Execution timed out 4072 ms 26604 KB Time limit exceeded
12 Halted 0 ms 0 KB -