Submission #1235255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235255		inesfi	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	1096 ms	26436 KiB

cleaning

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"

const int TAILLEMAXI=200*1000+2;
int nbnoeuds,nbquest;
vector<int> adja[TAILLEMAXI];
vector<int> nouv[TAILLEMAXI];
int racine;

pair<int,int> dp(int a,int vient){ // nb feuilles, cout
    if (nouv[a].size()==1){
        return {1,1};
    }
    pair<int,int> total={0,0};
    for (auto v:nouv[a]){
        if (v!=vient){
            pair<int,int> enfant=dp(v,a);
            total.first+=enfant.first;
            total.second+=enfant.second;
        }
    }
    if (a!=racine){
        if (total.first%2==1){
            return {1,total.second+1};
        }
        return {2,total.second+2};
    }
    return total;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>nbnoeuds>>nbquest;
    for (int i=0;i<nbnoeuds-1;i++){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        adja[a].push_back(b);
        adja[b].push_back(a);
    }
    racine=-1;
    int indice=0;
    while (racine==-1){
        if (adja[indice].size()!=1){
            racine=indice;
        }
        indice++;
    }
    for (int i=0;i<nbquest;i++){
        int enplus;
        cin>>enplus;
        for (int j=0;j<nbnoeuds+enplus;j++){
            nouv[j]=adja[j];
        }
        for (int j=0;j<enplus;j++){
            int val;
            cin>>val;
            nouv[val-1].push_back(nbnoeuds+j);
            nouv[nbnoeuds+j].push_back(val-1);
        }
        int nbfeuilles=0;
        for (int j=0;j<nbnoeuds+enplus;j++){
            if (nouv[j].size()==1){
                nbfeuilles++;
            }
        }
        if (nbfeuilles%2==1){
            cout<<-1<<endl;
        }
        else {
            cout<<dp(racine,-1).second<<endl;
        }
    }
    return 0;
}

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