Submission #1226985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226985		Faggi	Parachute rings (IOI12_rings)	C++20	37 / 100	2196 ms	184352 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;
set<pair<ll,ll>>s;
vector<ll>grafo[MAXN];

ll n, tim, vis[MAXN], id[MAXN], ars, nods, dif, dA, dN;
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;
}

void dfs2(ll nod, ll pad)
{
    nods++;
    vis[nod]=tim;
    for(auto k:grafo[nod])
    {
        ars++;
        if(k==pad||vis[k]>=tim)
            continue;
        dfs2(k,nod);
    }
    vis[nod]=tim+1;
}
vector<ll>Cant3;
ll ans3=0;
void cal(ll nod, ll cant, ll pad)
{
    ll aris=0;
    vis[nod]=tim;
    for(auto k:grafo[nod])
    {
        aris++;
        if(k==pad||vis[k]>=tim)
            continue;
        cal(k,cant,nod);
    }
    if(dN-1>dA-aris&&Cant3[nod]==cant)
        ans3++;

    vis[nod]=tim+1;
}

int CountCritical()
{
    vector<ll>cant3(n,0);
    ll res=0, ban, i, j, cant=0, cant2=0;
    ll cuat=0, pos;
    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++;
            cant2++;
        }
    }
    Cant3=cant3;
    ans3=0;
    if(cuat>1)
        return 0;
    tim=0;
    for(i=0; i<n; i++)
        vis[i]=0;
    if(cuat==1)
    {
        tim+=2;
        ban=0;
        i=pos;
        for(j=0; j<n; j++)
        {
            if(j==i)
                continue;
            if(vis[j]==tim+1)
                continue;
            if(dfs(j,0,i))
                ban=1;
        }
        if(cant3[pos]==cant&&ban==0)
            res++;
    }
    else
    {
        tim+=2;
        ll mal=0, raiz;
        vector<pair<ll,ll>>subs;
        for(i=0; i<n; i++)
        {
            if(vis[i]!=tim+1)
            {
                nods=0;
                ars=0;
                dfs2(i,-1);
                ars/=2;
                subs.pb({nods,ars});
                if(ars>=nods)
                {
                    mal++;
                    raiz=i;
                    dif=abs((nods-1)-ars);
                    dA=ars;
                    dN=nods;
                }

            }
        }
        if(mal==0)
        {
            ll ans2=0;
            for(i=0; i<n; i++)
                if(cant3[i]==cant)
                    ans2++;
            return ans2;
        }
        if(mal>1)
            return 0;
        if(mal==1)
        {
            tim+=2;
            Cant3=cant3;
            ans3=0;
            cal(raiz,cant2,-1);
            return ans3;
        }
        for(i=0; i<n; i++)
        {
            tim+=2;
            ban=0;
            for(j=0; j<n; j++)
            {
                if(j==i)
                    continue;
                if(vis[j]==tim+1)
                    continue;
                if(dfs(j,0,i))
                    ban=1;
            }
            if(ban==0&&cant3[i]==cant)
                res++;
        }
    }
    return res;
}
void Link(int a, int b)
{
    auto it=s.find({min(a,b),max(a,b)});
    if(it!=s.end())
        return;
    s.insert({min(a,b),max(a,b)});
    grafo[a].pb(b);
    grafo[b].pb(a);
    id[a]++;
    id[b]++;
}

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