Submission #412669

#	Time	Username	Problem	Language	Result	Execution time	Memory
412669		A_D	Parachute rings (IOI12_rings)	C++14	20 / 100	4088 ms	41484 KiB

rings

#include <bits/stdc++.h>

using namespace std;

int n;
const int N=1e6+100;
bool vis[N];
vector<int> g[N];
int ret;
int siz(int u,int p){
    int ret=0;
    for(auto x:g[u]){
        if(x==p)continue;
        ret++;
    }
    return ret;
}
void dfs(int u,int p,int me)
{
    vis[u]=1;
//    cout<<" u "<<u<<" "<<siz(u,me)<<endl;
    if(siz(u,me)>2){
        ret=0;
    }
    for(auto x:g[u]){
  //      cout<<" x "<<x<<" "<<siz(x,me)<<" "<<vis[x]<<" "<<me<<" "<<p<<endl;
        if(x==p||x==me)continue;
        if(vis[x]){
            ret=0;
            return;
        }
        dfs(x,u,me);
    }
}
int ok(int u)
{
    memset(vis,0,sizeof(vis));
    vis[u]=1;
    ret=1;
    for(int i=0;i<n;i++){
        int sz=siz(i,u);
        if(vis[i]==0&&sz<=1){
            dfs(i,i,u);
        }
    }
    for(int i=0;i<n;i++){
        if(vis[i]==0){
            ret=0;
        }
    }
    return ret;
}

void Init(int N_) {
    n = N_;
}

void Link(int a, int b){
    g[a].push_back(b);
    g[b].push_back(a);
}

int CountCritical() {
    int ans=0;
    for(int i=0;i<n;i++){
        ans+=ok(i);
    //    return ans;
    }
    return ans;
}

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