Submission #428896

#	Time	Username	Problem	Language	Result	Execution time	Memory
428896		ocarima	Star Trek (CEOI20_startrek)	C++14	7 / 100	1 ms	340 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 t = 1;
    repv(h, hijos[nodo]){
        if (h == padre) continue;
        t *= dfs(h, nodo);
    }

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

void dfstipos(lli nodo, lli padre, lli tipopadre){

    // SI YO SOY GANADOR, SEGUIRE SIENDO GANADOR SIN IMPORTAR LO QUE PASE, YA QUE TENGO AL MENOS UN PERDEDOR EN MI SUBARBOL
    if (tipooriginal[nodo] == ganador) tipo[nodo] = ganador;
    else{
        // SI YO SOY PERDEDOR TODOS MIS HIJOS SON GANADORES, SI EL QUE VIENE DE LA RAIZ ES PERDEDOR YO ME VUELVO GANADOR, DE OTRA FORMA SIGO SIENDO PERDEDOR.
        if (tipopadre == perdedor) tipo[nodo] = ganador;
        else tipo[nodo] = perdedor;
    }

    repv(h, hijos[nodo]){
        if (h == padre) continue;

        if (nodo == 1) dfstipos(h, nodo, perdedor); // SI EL PADRE ES LA RAIZ, SIEMPRE SERA PERDEDORA
        else{
            // SI NO ES LA RAIZ, DEPENDE DE SUS HIJOS Y EL PADRE, SI
            // EN EL TIPO ORIGINAL ERA GANADOR, SIGNIFICA QUE EN SU SUBARBOL HAY AL MENOS 1 PERDEDOR, POR LO QUE ES GANADOR
            // SI EN EL TIPO ORIGINAL ERA PERDEDOR, TODOS SON GANADORES Y DEPENDE DEL TIPO DE SU PADRE.
            if (tipooriginal[nodo] == ganador) dfstipos(h, nodo, ganador);
            else if (tipopadre == ganador) dfstipos(h, nodo, perdedor);
            else dfstipos(h, nodo, 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
    tipo[1] = dfs(1, 0);
    dfstipos(1, 0, ganador);

    // 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)) % MOD;
    else cout << (cntcriticos * totp) % MOD;


    return 0;
}

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