Submission #61783

#	Time	Username	Problem	Language	Result	Execution time	Memory
61783		theknife2001	Parachute rings (IOI12_rings)	C++17	20 / 100	4035 ms	1324 KiB

rings

#include <bits/stdc++.h>


using namespace std;
const int N=5005;
vector < int > vec[N];
int n;
bool visited[N];

void Init(int N_) {
  n = N_;

}

void Link(int A, int B) {
    vec[A].push_back(B);
    vec[B].push_back(A);
}

bool dfs(int u , int p , int black)
{
    visited[u]=1;
    bool q=0;
    int cnt=0;
    for(auto v:vec[u])
    {
        if(v==black||v==p)
            continue ;
        if(visited[v])
            return 1;
        cnt++;
        q|=dfs(v,u,black);
    }
    if(cnt>=2&&p!=-1)
        q=1;
    if(p==-1&&cnt>2)
        q=1;
    return q;
}

int CountCritical() {
    int ans=0;
    bool q;
    for(int i=0;i<n;i++)
    {
        q=0;
        memset(visited,0,sizeof visited);
        for(int j=0;j<n;j++)
        {
            if(visited[j]==0&&j!=i)
                q|=dfs(j,-1,i);
        }
        if(!q)
            ans++;
    }
    return ans;
}

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