oj.uz

답안 #432145

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
432145 2021-06-17T21:45:36 Z ocarima Spring cleaning (CEOI20_cleaning) C++14
16 / 100
 1000 ms 22896 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 MAX_N 100003

lli n, q, a, b, d, raiz, tiempo, hoja, paridad;
vector<int> hijos[MAX_N];
lli tam[MAX_N], hojas[MAX_N], p[MAX_N], hijomayor[MAX_N], visto[MAX_N], hld[MAX_N], hojaextendida[MAX_N];
lli segtree[MAX_N << 1], lazy[MAX_N << 1];

void dfs(lli nodo, lli padre){
    p[nodo] = padre;
    tam[nodo] = 1; // EL MISMO
    if (hijos[nodo].size() == 1) hojas[nodo] = 1;

    for(auto h : hijos[nodo]){
        if (h == padre) continue;
        dfs(h, nodo);
        tam[nodo] += tam[h]; // AGREGA AL SUBARBOL DEL PADRE EL TAMAÑO DEL SUBARBOL DEL HIJO
        hojas[nodo] += hojas[h]; // AGREGA AL PADRE TODAS LAS HOJAS DEL HIJO
        if (hijomayor[nodo] == 0 || tam[h] > tam[hijomayor[nodo]]) hijomayor[nodo] = h; // GUARDA EL HIJO MAYOR PARA EL HLD
    }
}

void HLD(lli nodo, lli padre){
    if (padre == 0) hld[nodo] = nodo; // SI ES LA RAIZ, ES CABEZA DE SU RAMA DE HLD

    visto[nodo] = ++tiempo; // MARCA EL TIEMPO EN QUE VISITASTE ESTE NODO.  LA RAIZ SE VE EN EL TIEMPO 1
    if (hijomayor[nodo]){
        hld[hijomayor[nodo]] = hld[nodo]; // ASIGNA A TU HIJO MAYOR A LA MISMA RAMA QUE TU
        HLD(hijomayor[nodo], nodo); // BAJA POR EL HIJO MAYOR, ASUMIENDO QUE EXISTE
    }

    for(auto h : hijos[nodo]){
        if (h == padre || h == hijomayor[nodo]) continue;
        hld[h] = h; // CREA UNA NUEVA RAMA PARA CADA HIJO QUE NO ES EL MAYOR.
        HLD(h, nodo);
    }
}

void push(lli nodo, lli s, lli e){
    if (!lazy[nodo]) return; // SI NO HAY NADA QUE HACER SAL.

    segtree[nodo] = (e - s + 1) - segtree[nodo]; // CAMBIA LA SUMA DEL NODO AL INVERSO, LOS QUE ANTES SUMABAN AHORA NO Y VICEVERSA

    if (s < e){ // SI EL RANGO TIENE HIJOS
        lazy[nodo * 2] ^= 1;
        lazy[nodo * 2 + 1] ^= 1;  // HAZLES TOGGLE A SUS NODOS
    }

    lazy[nodo] = 0; // LIMPIA EL LAZY
}

void updatest(lli nodo, lli s, lli e, lli l, lli r, lli val){
    push(nodo, s, e);
    if (s > r || e < l) return;
    if (s >= l && e <= r){
        lazy[nodo] ^= val;
        push(nodo, s, e);
        return;
    }

    // ACTUALIZA AMBOS LADOS
    lli mitad = (s + e) / 2;
    updatest(nodo * 2, s, mitad, l, r, val);
    updatest(nodo * 2 + 1, mitad + 1, e, l, r, val);

    // HAZ EL MERGE
    segtree[nodo] = segtree[nodo * 2] + segtree[nodo * 2 + 1];
}

void updatehld(lli nodo){
    while (nodo > 0){ // MIENTRAS NO LLEGUE A LA RAIZ

        // ACTUALIZA EL RANGO DEL SEGMENT TREE QUE VA DEL MOMENTO EN QUE SE VIO EL PADRE DE LA CADENA/RAMA DEL HLD AL QUE PERTENECE HASTA EL NODO QUE SE DESEA ACTUALIZAR.
        updatest(1, 1, tiempo, visto[hld[nodo]], visto[nodo], 1);

        nodo = p[hld[nodo]]; // MUEVETE AL PADRE DE LA CADENA ACTUAL DEL HLD
    }
}

lli getroot(lli nodo, lli s, lli e){
    // LA RAZON DE HACER ESTA FUNCION ES QUE SE PROPAGUE CUALQUIER PUSH QUE HUBIERA QUEDADO SUELTO EN EL CAMINO AL NODO 1
    push(nodo, s, e);
    if (s == 1 && e == 1) return segtree[nodo];
    lli mitad = (s + e) / 2;

    // VE SOLO AL LADO IZQUIERDO YA QUE SOLO NOS INTERESA EL NODO 1
    return getroot(nodo * 2, s, mitad);
}

int main()
{
    fastio;

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

    // UTILIZA COMO RAIZ UN NODO QUE NO SEA HOJA.
    rep(i, 1, n) if(hijos[i].size() > 1){
        raiz = i;
        break;
    }

    // HAZ EL PRECALCULO DE TODO EL ARBOL, tam del subarbol (para el HLD), cantidad de hojas en subarbol (para saber su paridad), padre (para poder subir en el HLD)
    dfs(raiz, 0);

    // DESCOMPON EL ARBOL EN CADENAS CON UN HEAVY-LIGHT DECOMPOSITION
    HLD(raiz, 0);

    // ACTUALIZA EL SEGMENT TREE DEL ARBOL ORIGINAL CON LAS PARIDADES DE CADA ARBOL, LOS NODOS PARES AGREGAN UNO EXTRA AL COSTO.
    rep(i, 1, n) updatest(1, 1, tiempo, visto[i], visto[i], !(hojas[i] & 1));

    rep(i, 1, q){
        cin >> d;

        vector<int> nuevashojas(d, 0);
        rep(j, 0, d - 1) cin >> nuevashojas[j];

        // AGREGA LAS HOJAS
        rep(j, 0, d - 1){
            hoja = nuevashojas[j];
            if (hijos[hoja].size() == 1 && !(hojaextendida[hoja])){
                // ES UNA HOJA PERO ESTE ES SU PRIMER NODO, ENTONCES NO DEBE AFECTAR, PARA HACER MAS SENCILLO EL CODIGO
                // SE HARA UNA DOBLE ACTUALIZACION PARA QUE QUEDE IGUAL Y SE MARCA COMO QUE YA SE EXTENDIO
                hojaextendida[hoja] = 1;

                // ACTUALIZA TODO EL HLD
                updatehld(hoja);
            }
            updatehld(hoja); // ACTUALIZA
        }

        // CHECA LA RAIZ
        paridad = getroot(1, 1, tiempo); // OBTEN LA PARIDAD DE LA RAIZ CON ESTE ARBOL
        if (!(paridad & 1)) cout << "-1\n"; // SI EL NODO NO SUMA DOBLE (NO ES PAR) ENTONCES NO SE PUEDE RESOLVER.
        else cout << n + d + segtree[1] - 2 << "\n"; // LA RAZON DE RESTAR 2 ES QUE EL TOTAL DE ARISTAS ES (n - 1) Y SE DEBE QUITAR EL EXTRA QUE IRIA DE LA RAIZ A SU PADRE

        // QUITA LAS HOJAS
        rep(j, 0, d - 1){
            hoja = nuevashojas[j];
            if (hijos[hoja].size() == 1 && hojaextendida[hoja]){
                // QUITA EL DOBLE
                hojaextendida[hoja] = 0;
                updatehld(hoja);
            }
            updatehld(hoja);
        }
    }

    return 0;
}

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 418 ms 6248 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 3788 KB Output is correct
2 Correct 84 ms 3788 KB Output is correct
3 Incorrect 99 ms 14272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 4472 KB Output is correct
2 Correct 68 ms 4488 KB Output is correct
3 Incorrect 132 ms 22896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 6852 KB Output is correct
2 Correct 145 ms 5856 KB Output is correct
3 Correct 20 ms 5580 KB Output is correct
4 Correct 26 ms 5960 KB Output is correct
5 Correct 29 ms 6332 KB Output is correct
6 Correct 131 ms 6452 KB Output is correct

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 592 ms 11760 KB Output is correct
2 Correct 951 ms 11684 KB Output is correct
3 Correct 758 ms 7552 KB Output is correct
4 Correct 983 ms 11640 KB Output is correct
5 Execution timed out 1008 ms 11656 KB Time limit exceeded

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 745 ms 16772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 418 ms 6248 KB Output is correct
3 Correct 83 ms 3788 KB Output is correct
4 Correct 84 ms 3788 KB Output is correct
5 Incorrect 99 ms 14272 KB Output isn't correct
6 Halted 0 ms 0 KB -