Submission #428845

#	Time	Username	Problem	Language	Result	Execution time	Memory
428845		ocarima	Star Trek (CEOI20_startrek)	C++14	30 / 100	24 ms	460 KiB

startrek

#include<bits/stdc++.h>

using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
#define lli long long
#define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
#define repa(i, a, b) for(lli i = (a); i >= (b); --i)
#define repv(i, x) for(auto i : x)

#define nl "\n"
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << nl
#define debugarr(x, a, b) cout << #x << " = ["; rep(ii, a, b){ cout << x[ii] << ", "; } cout << "]" << nl

#define MOD 1000000007
#define MAX_N 1003

#define perdedor 0
#define ganador 1

lli n, d, a, b, tipo[MAX_N], tipooriginal[MAX_N], critico[MAX_N], cntcriticos, totg, totp;
vector<lli> hijos[MAX_N];


lli binexp(lli b, lli e){
    lli res = 1;
    while (e > 0){
        if (e & 1) res = (res * b) % MOD;
        e >>= 1;
        b = (b * b) % MOD;
    }
    return res;
}

lli dfs(lli nodo, lli padre, lli raiz){
    lli t = 1;
    repv(h, hijos[nodo]){
        if (h == padre) continue;
        t *= dfs(h, nodo, raiz);
    }

    if (t){
        if (raiz == 1) tipooriginal[nodo] = perdedor;
        return perdedor;
    }
    else {
        if (raiz == 1) tipooriginal[nodo] = ganador;
        return ganador;
    }
}

void dfscriticos(lli nodo, lli padre){
    lli cnt = 0;
    repv(h, hijos[nodo]){
        if (h == padre) continue;
        if (tipooriginal[h] == perdedor) ++cnt;
    }

    if (cnt > 1) return; // SI TIENE MAS DE UN HIJO PERDEDOR, NADIE EN SU SUBARBOL PUEDE SER CRITICO
    if (tipooriginal[nodo] == perdedor){
        // SI ES UN NODO PERDEDOR Y LA BUSQUEDA LLEGO A EL, SIGNIFICA QUE EN SU CAMINO A LA RAIZ
        // NO HAY NINGUN GANADOR CON MAS DE UN HIJO PERDEDOR, POR LO QUE UN CAMBIO EN ESTE NODO
        // IMPLICA QUE SE PROPAGA HASTA LA RAIZ.
        critico[nodo] = 1;
        ++cntcriticos;
    }

    repv(h, hijos[nodo]){
        if (h == padre) continue;
        if (tipooriginal[nodo] == perdedor || (tipooriginal[nodo] == ganador && tipooriginal[h] == perdedor)) dfscriticos(h, nodo);
    }

}

int main()
{
    fastio;

    cin >> n >> d;

    if (n == 2){ cout << binexp(4, d); return 0; }
    else if (n > 1000) return 0;

    rep(i, 1, n - 1){
        cin >> a >> b;
        hijos[a].push_back(b);
        hijos[b].push_back(a);
    }

    // VERIFICA DE QUE TIPO ES CADA NODO
    rep(i, 1, n) tipo[i] = dfs(i, 0, i);

    // CUENTA LOS PUNTOS QUE SON CRITICOS.
    // LOS PUNTOS CRITICOS SON LOS NODOS PERDEDORES QUE EN SU CAMINO A LA RAIZ NO TIENEN NINGUN NODO GANADOR CON DOS O MAS HIJOS PERDEDORES,
    // ES DECIR, SI ELLOS CAMBIAN A GANADOR LOS NODOS EN SU CAMINO A LA RAIZ TAMBIEN CAMBIARAN HACIENDO POR TANTO CAMBIAR A LA RAIZ
    dfscriticos(1, 0);

    // LOS NODOS QUE PUEDEN CAMBIAR EL RESULTADO SON LOS NODOS CRITICOS.  EN ESOS NODOS SI SE CONECTA A UN PERDEDOR DEL OTRO LADO CAMBIARA EL VALOR DE LA RAIZ
    // ENTONCES...

    // SI LA RAIZ ES GANADORA, TODOS LOS NODOS CRITICOS NO DEBEN CONECTARSE A PERDEDORES Y CUALQUIER OTRO NO IMPORTA, EL TOTAL ES ((n - cntcriticos) * n) + (cntcriticos * ganadores)
    // SI LA RAIZ ES PERDEDORA, SOLO CAMBIA CONECTANDO LOS CRITICOS A LOS PERDEDORES, EL TOTAL ES (criticos * perdedores)

    rep(i, 1, n) if (tipo[i] == perdedor) ++totp;
    totg = n - totp;

    if (tipooriginal[1] == ganador) cout << (n * n) - (cntcriticos * totp);
    else cout << cntcriticos * totp;


    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15