Submission #350839

#	Time	Username	Problem	Language	Result	Execution time	Memory
350839		juggernaut	Parachute rings (IOI12_rings)	C++14	0 / 100	4090 ms	26428 KiB

rings

#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>3){
        if(cnt!=1)mx=2e9;
        global_ans=0;
    }
    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 (stderr)

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

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31