Submission #350322

#	Time	Username	Problem	Language	Result	Execution time	Memory
350322		juggernaut	Parachute rings (IOI12_rings)	C++14	55 / 100	4062 ms	74220 KiB

rings

#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;
}
void Init(int N){n=N;}
void Link(int x,int y){
    g[x].push_back(y);
    g[y].push_back(x);
    deg[x]++;
    deg[y]++;
}
int CountCritical(){
    int mx=-1,cnt=0;
    for(int i=0;i<n;i++)
        if(deg[i]>mx){
            mx=deg[i];
            cnt=1;
        }else if(deg[i]==mx)cnt++;
    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;
            }
        }
    }
}

Compilation message (stderr)

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

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