제출 #1226947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226947		Faggi	낙하산 고리들 (IOI12_rings)	C++20	0 / 100	4096 ms	168828 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
using namespace std;
const int MAXN=1e6+1;

vector<ll>grafo[MAXN];
map<ll,bool>m[MAXN];

ll n, id[MAXN], 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;
}

bool ciclo(ll nod)
{
    tim+=2;
    for(auto k:grafo[nod])
    {
        if(dfs(k,nod,nod))
            return 1;
    }
    return 0;
}

int CountCritical()
{
    ll cuat=0, pos, cant=0, i;
    vector<ll>can(n,0),cant3(n,0);
    for(i=0; i<n; i++)
        vis[i]=0;
    tim=0;
    for(i=0; i<n; i++)
    {
        if(id[i]>=4)
        {
            cuat++;
            pos=i;
        }
        else if(id[i]==3)
        {
            for(auto k:grafo[i])
                cant3[k]++;
            cant3[i]++;
            cant++;
        }
    }
    if(cuat>1)
        return 0;
    if(cuat==1)
    {
        if(cant3[pos]==cant&&ciclo(pos)==0)
            return 1;
        else
            return 0;
    }
    ll ans=0;
    for(i=0; i<n; i++)
    {
        if(cant3[i]==cant&&ciclo(i)==0)
            ans++;
    }
    return ans;
}

void Link(int a, int b)
{
    if(m[a][b]==1)
        return;
    m[a][b]=1;
    m[b][a]=1;
    grafo[a].pb(b);
    grafo[b].pb(a);
    id[a]++;
    id[b]++;
}

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