Submission #431366

#	Time	Username	Problem	Language	Result	Execution time	Memory
431366		Ozy	Spring cleaning (CEOI20_cleaning)	C++17	18 / 100	1091 ms	33720 KiB

cleaning

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000

lli n,a,b,raiz,q,total, x;
lli res[MAX+2],hojas[MAX+2],paridad[MAX+2];
vector<lli> hijos[MAX+2];
map<lli,lli> mapa[MAX+2];

void ch(lli pos, lli padre) {

    if (hijos[pos].size() == 1) hojas[padre]++;

    for (auto h : hijos[pos]) {
        if (h == padre) continue;
        ch(h,pos);
        hojas[pos] += hojas[h];
    }

}

void DFS (lli pos, lli padre) {

    lli query, cant;

    for (auto h : hijos[pos]) {
        if (h == padre) continue;

        // BAJA PRIMERO A TODOS TUS HIJOS
        DFS(h,pos);

        // HAY QUE HACER UN SMALL-TO-LARGE
        if (mapa[pos].size() < mapa[h].size()) swap(mapa[pos], mapa[h]);

        for (auto act : mapa[h]) {
            query = act.first;
            cant = act.second;

            // SI EN AMBOS MAPAS ESTA AFECTADO ESE QUERY, HAY QUE VER SI SE CANCELAN,
            // SE CANCELAN SI ESTA EN AMBOS Y LA SUMA DE AMBOS ES PAR
            if (mapa[pos].find(query) != mapa[pos].end()){
                mapa[pos][query] += cant;
                if (!(mapa[pos][query] % 2)) mapa[pos].erase(query);
                else mapa[pos][query] %= 2;
            }
            else mapa[pos][query] += cant; // SI NO ESTA EN EL MAPA DEL NODO, AGREGALO
        }
    }

    if (hijos[pos].size() == 1){
        vector<int> paraborrar;
        // SI EL NODO ES UNA HOJA, AFECTA EL COSTO SI TIENE UN NUMERO PAR DE AGREGADOS
        for (auto act : mapa[pos]){
            query = act.first;
            cant = act.second;

            if (cant == 1) paraborrar.push_back(query); // SI LA CANTIDAD DE NODOS ES IMPAR NO SE AFECTA EL COSTO, BORRA LA ENTRADA
            else if (cant == 2) res[query]++; // AUMENTA EN 1 EL COSTO PARA ESE QUERY
        }

        for(auto b : paraborrar) mapa[pos].erase(b);
    }
    else if (pos == raiz){
        // SI EL NODO ES LA RAIZ ENTONCES DEBE SER INVALIDO EN TODOS LOS CASOS EN DONDE LA PARIDAD SEA IMPAR
        for (auto act : mapa[pos]){
            query = act.first;
            cant = act.second;

            if (cant == 1 && paridad[raiz] == 0) res[query] = -1;
            else if (cant == 2 && paridad[raiz] == 0) res[query] = -1;
        }

        if (paridad[raiz] == 1){
            rep(i, 1, q) if (mapa[raiz].find(i) == mapa[raiz].end()) res[i] = -1;
        }
    }
    else{
        // SI EL NODO NO ES HOJA, DEBE AFECTAR EL COSTO EN TODOS LOS QUERYS DONDE TENGA HIJOS,
        for (auto act : mapa[pos]){
            query = act.first;
            cant = act.second;

            if (cant == 1 && paridad[pos] == 1) res[query]++; // SI EL NODO ERA IMPAR Y HAY UN NUEVO HIJO, SE VUELVE PAR Y AUMENTA EL COSTO
            else if (cant == 1 && paridad[pos] == 0) res[query]--; // SI ERA PAR Y SE LE AGREGA UNO, SE VUELE IMPAR Y DISMINUYE EL COSTO
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

        if (raiz == -1) {
            if (hijos[a].size() > 1) raiz = a;
            if (hijos[b].size() > 1) raiz = b;
        }
    }

    // CUENTA EL NUMERO DE HOJAS EN CADA SUBARBOL
    ch(raiz, 0);

    // CALCULA UNA PARIDAD PARA CADA NODO, LOS NODOS CON PARIDAD PAR TENDRAN QUE LIMPIAR DOBLE SU ARISTA PADRE
    rep (i,1,n) {
        if (raiz == i){
            if (hojas[i] & 1) paridad[raiz] = 1;
            else paridad[raiz] = 0;
            continue; // LA RAIZ NO IMPORTA SU PARIDAD PORQUE NO TIENE UN PADRE A QUIEN SUBIR
        }
        if (hojas[i] == 0 || (hojas[i]&1)) paridad[i] = 1; // SE CONSIDERA QUE LAS HOJAS TIENEN PARIDAD IMPAR
        else {paridad[i] = 0; total++;}
    }

    rep(i,1,q) {
        // LEE TODOS LOS QUERIES EN SIMULTANEO
        cin >> x;

        // INICIALIZA EL RESULTADO INICIAL DE CADA QUERY AL COSTO DEL ARBOL MAS LAS ARISTAS QUE SE ESTAN AGREGANDO
        res[i] = n - 1 + total + x;

        rep(j,1,x) {
            cin >> a;

            // SI A UN QUERY NO-HOJA SE LE AGREGA UN NUMERO PAR DE NODOS, ESTOS SE CANCELAN ENTRE ELLOS Y NO CAMBIO EL RESTO DEL ARBOL
            if (mapa[a].find(i) != mapa[a].end() && hijos[a].size() > 1) mapa[a].erase(i);
            else {
                if (hijos[a].size() > 1) mapa[a][i]++; // SI NO ES HOJA, AGREGALE EL NODO EN EL QUERY CORRESPONDIENTE
                else{
                    // SI ES UNA HOJA ENTONCES NO SE PUEDEN CANCELAR LOS PRIMEROS DOS NODOS
                    mapa[a][i]++;
                    if (mapa[a][i] > 2) mapa[a][i] -= 2;
                }
            }
        }
    }

    DFS(raiz, 0);

    rep(i, 1, q) cout << res[i] << "\n";
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30