Submission #596055

#	Time	Username	Problem	Language	Result	Execution time	Memory
596055		BT21tata	Parachute rings (IOI12_rings)	C++17	20 / 100	4094 ms	82252 KiB

rings

#include <bits/stdc++.h>
using namespace std;
int n;
bool used[10005];
vector<int>g[1000005];

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

void Link(int A, int B)
{
    g[A+1].push_back(B+1);
    g[B+1].push_back(A+1);
}

bool dfs(int v, int p, int d)
{
    //cout<<"ok  "<<v<<' '<<p<<' '<<d<<' ';
    used[v]=1;
    int cnt=0;
    bool f=1;
    for(int u : g[v])
    {
        if(u!=d)
        {
            cnt++;
            if(u!=p)
            {
                if(!used[u]) f&=dfs(u, v, d);
                else return 0;
            }
        }
    }
    //cout<<"cnt "<<cnt<<endl;
    if(cnt>2) return 0;
    return f;
}

int CountCritical()
{
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        bool ok=1;
        memset(used, 0, sizeof(used));
        for(int j=1; j<=n; j++)
        {
            if(!used[j] and j!=i) ok&=dfs(j, 0, i);
        }
        ans+=ok;
        //cout<<i<<' '<<ok<<endl;
    }
    return ans;

}

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