제출 #432145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432145		ocarima	Spring cleaning (CEOI20_cleaning)	C++14	16 / 100	1008 ms	22896 KiB

cleaning

#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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 16 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30