oj.uz

Submission #428845

# Submission time Handle Problem Language Result Execution time Memory
428845 2021-06-15T14:51:22 Z ocarima Star Trek (CEOI20_startrek) C++14
30 / 100
 24 ms 460 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 18 ms 388 KB Output isn't correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 18 ms 460 KB Output is correct
8 Correct 24 ms 452 KB Output is correct
9 Correct 11 ms 332 KB Output is correct
10 Correct 16 ms 396 KB Output is correct
11 Correct 18 ms 332 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 18 ms 460 KB Output is correct
8 Correct 24 ms 452 KB Output is correct
9 Correct 11 ms 332 KB Output is correct
10 Correct 16 ms 396 KB Output is correct
11 Correct 18 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 18 ms 460 KB Output is correct
8 Correct 24 ms 452 KB Output is correct
9 Correct 11 ms 332 KB Output is correct
10 Correct 16 ms 396 KB Output is correct
11 Correct 18 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Incorrect 16 ms 332 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 18 ms 460 KB Output is correct
8 Correct 24 ms 452 KB Output is correct
9 Correct 11 ms 332 KB Output is correct
10 Correct 16 ms 396 KB Output is correct
11 Correct 18 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 18 ms 388 KB Output isn't correct