Submission #1226956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226956		Faggi	Parachute rings (IOI12_rings)	C++20	20 / 100	4094 ms	47964 KiB

rings

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;
const int MAXN=1e6+1;

vector<ll>grafo[MAXN];

ll n, tim, vis[MAXN];
void Init(int N)
{
    n=N;
}

bool dfs(ll nod, ll pad, ll prob)
{
    vis[nod]=tim;
    for(auto k:grafo[nod])
    {
        if(k==pad||k==prob||vis[k]==tim+1)
            continue;
        if(vis[k]==tim)
            return 1;
        if(dfs(k,nod,prob))
            return 1;
    }
    vis[nod]=tim+1;
    return 0;
}

int CountCritical()
{
    ll res=0, ban, i, j, cant;
    tim=0;
    memset(vis,0,sizeof(vis));
    for(i=0; i<n; i++)
    {
        tim+=2;
        ban=0;
        for(j=0; j<n; j++)
        {
            if(j==i)
                continue;
            cant=0;
            for(auto k:grafo[j])
            {
                if(k==i)
                    continue;
                cant++;
            }
            if(cant>2)
                ban=1;
            if(vis[j]==tim+1)
                continue;
            if(dfs(j,0,i))
                ban=1;
        }
        if(ban==0)
            res++;
    }
    return res;
}
void Link(int a, int b)
{
    grafo[a].pb(b);
    grafo[b].pb(a);
}

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