Submission #1226995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226995		Faggi	Parachute rings (IOI12_rings)	C++20	37 / 100	2148 ms	149096 KiB

rings

#include <bits/stdc++.h>
#define ll int
#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 fr first
#define se second
using namespace std;

const int MAXN = 1e6 + 1;
set<pair<ll,ll>> s;
vector<ll> grafo[MAXN];
ll n;
int vis[MAXN], id[MAXN];
vector<ll> cant3;
ll nods, ars, dA, dN, ans3;

// DFS para detección de ciclo ignorando 'pad' y 'prob'
bool dfs(int nod, int pad, int prob) {
    vis[nod] = 1; // en recursión
    for (int k : grafo[nod]) {
        if (k == pad || k == prob || vis[k] == 2) continue;
        if (vis[k] == 1) return true;
        if (dfs(k, nod, prob)) return true;
    }
    vis[nod] = 2; // totalmente procesado
    return false;
}

// DFS para contar nodos (nods) y aristas (ars) en componente
void dfs2(int nod, int pad) {
    nods++;
    vis[nod] = 1;
    for (int k : grafo[nod]) {
        ars++;
        if (k == pad || vis[k]) continue;
        dfs2(k, nod);
    }
    vis[nod] = 2;
}

// DFS para el cálculo de ans3 en la fase raíz
void cal(int nod, ll cant, int pad) {
    ll aris = 0;
    vis[nod] = 1;
    for (int k : grafo[nod]) {
        aris++;
        if (k == pad || vis[k]) continue;
        cal(k, cant, nod);
    }
    if ((dN - 1) > (dA - aris) && cant3[nod] == cant)
        ans3++;
    vis[nod] = 2;
}

void Init(int N) {
    n = N;
    s.clear();
    cant3.clear();
    cant3.resize(n, 0);
    for (int i = 0; i < n; i++) {
        grafo[i].clear();
        vis[i] = 0;
        id[i] = 0;
    }
}

// Cuenta los nodos críticos según la lógica original, pero reinicializando vis[]
int CountCritical() {
    // Limpiamos marcas de visita
    for (int i = 0; i < n; i++) vis[i] = 0;
    ll res = 0, cant = 0, cuat = 0, pos = -1, mal = 0, raiz = -1, ans2 = 0;
    ans3 = 0;

    // Recalculamos cant3 y contamos cuántos id>=4
    fill(cant3.begin(), cant3.end(), 0);
    for (int i = 0; i < n; i++) {
        if (id[i] >= 4) {
            cuat++;
            pos = i;
        } else if (id[i] == 3) {
            cant++;
            for (int k : grafo[i])
                cant3[k]++;
            cant3[i]++;
        }
    }
    if (cuat > 1) return 0;

    if (cuat == 1) {
        // Caso único con grado>=4
        // Comprobamos ciclo al remover pos
        for (int j = 0; j < n; j++) {
            if (j == pos) continue;
            if (!vis[j]) {
                if (dfs(j, -1, pos))
                    return 0;
            }
        }
        if (cant3[pos] == cant)
            res = 1;
        return res;
    } else {
        // Sin nodos de grado>=4: buscamos componente “mala”
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                nods = ars = 0;
                dfs2(i, -1);
                ars /= 2;
                if (ars >= nods) {
                    mal++;
                    raiz = i;
                    dA = ars;
                    dN = nods;
                }
            }
        }
        if (mal == 0) {
            // Ninguna componente con aristas>=nodos
            for (int i = 0; i < n; i++)
                if (cant3[i] == cant)
                    ans2++;
            return ans2;
        }
        if (mal > 1) return 0;

        // Una sola componente “mala”: recalculamos ans3
        for (int i = 0; i < n; i++) vis[i] = 0;
        cal(raiz, cant, -1);
        return ans3;
    }
}

void Link(int a, int b) {
    auto e = make_pair(min(a,b), max(a,b));
    if (s.count(e)) return;
    s.insert(e);
    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