oj.uz

답안 #431332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431332 2021-06-17T11:02:25 Z Ozy Spring cleaning (CEOI20_cleaning) C++17
9 / 100
 233 ms 33744 KB 
#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) 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 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Incorrect 115 ms 16600 KB Output isn't correct

Subtask #2
0 / 9.0

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

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 8692 KB Output is correct
2 Correct 18 ms 8776 KB Output is correct
3 Correct 67 ms 21640 KB Output is correct
4 Correct 93 ms 25584 KB Output is correct
5 Correct 72 ms 26432 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 28616 KB Output is correct
2 Incorrect 157 ms 22796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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

Subtask #7
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Incorrect 115 ms 16600 KB Output isn't correct