Submission #1235278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235278		kaltspielerhy	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	1097 ms	10772 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
const int INFINI = 1e9;

vector<vector<int>> graphe;
int N, Q;

int solve() {
    vector<int> parent(N);
    vector<int> nbEnfants(N, 0);
    vector<int> feuilles;
    // cerr << "done";
    // Trouver la racine
    vector<int> distances(N, INFINI);
    queue<int> bfs;
    for (int iNoeud = 0; iNoeud < N; iNoeud++) {
        if (graphe[iNoeud].size() == 1) {
            bfs.push(iNoeud);
            nbEnfants[iNoeud] = 0;
            feuilles.push_back(iNoeud);
        }
    }
    // cerr << feuilles.size();
    if (feuilles.size() % 2 == 1) return -1;
    // cerr << "done";
    int distance = 0;
    while (!bfs.empty()) {
        int taille = bfs.size();
        for (int i = 0; i < taille; i++) {
            int noeud = bfs.front();
            bfs.pop();

            if (distances[noeud] != INFINI) continue;
            distances[noeud] = distance;
            
            for (int iVoisin : graphe[noeud]) {
                if (distances[iVoisin] != INFINI) bfs.push(iVoisin);
            }
        } 
        distance++;
    }

    int distMax = -1, noeudMax = -1;
    for (int i = 0; i < N; i++) {
        if (distances[i] > distMax) {
            distMax = distances[i];
            noeudMax = i;
        }
    }
    // cerr << "done";
    parent[noeudMax] = -1;
    // L'enraciner
    bfs.push(noeudMax);
    vector<bool> visited(N);
    while (!bfs.empty()) {
        int noeud = bfs.front();
        bfs.pop();

        if (visited[noeud]) continue;
        visited[noeud] = true;

        for (int iVoisin : graphe[noeud]) {
            if (!visited[iVoisin]) {
                parent[iVoisin] = noeud;
                nbEnfants[noeud]++;
                bfs.push(iVoisin);
            }
        }
    }
    // cerr << "done";
    vector<pair<int, int>> storage(N, {0, 0});
    for (int i : feuilles) {
        bfs.push(i);
        storage[i].first++;
    }

    int res = 0;

    while (!bfs.empty()) {
        int noeud = bfs.front();
        bfs.pop();

        if (parent[noeud] == -1) {
            break;
        }

        while (storage[noeud].first > 2) {
            storage[noeud].first -= 2;
        }

        while (storage[noeud].second > 0 && (storage[noeud].first > 0 || storage[noeud].second > 1)) {
            storage[noeud].second--;
        }

        storage[parent[noeud]].first += storage[noeud].first;
        storage[parent[noeud]].second += storage[noeud].second;
        res += storage[noeud].first;
        res += storage[noeud].second*2;

        nbEnfants[parent[noeud]]--;
        if (nbEnfants[parent[noeud]] == 0) bfs.push(parent[noeud]);
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> Q;
        
    graphe.resize(2*N+2);

    for (int i = 0; i < N-1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        graphe[u].push_back(v);
        graphe[v].push_back(u);
    }

    for (int i = 0; i < Q; i++) {
        int nbFeuilles;
        cin >> nbFeuilles;
        vector<int> feuilles(nbFeuilles);
        for (int& i2 : feuilles) cin >> i2;
        for (int i2 = 0; i2 < nbFeuilles; i2++) {
            graphe[feuilles[i2]-1].push_back(N+i2);
            graphe[N+i2].push_back(feuilles[i2]-1);
        }
        N += nbFeuilles;

        cerr << solve() << '\n';

        N -= nbFeuilles;

        for (int i2 = 0; i2 < nbFeuilles; i2++) {
            graphe[feuilles[i2]-1].pop_back();
            graphe[N+i2].pop_back();
        }
    }
}

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