Submission #1235112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235112		oscar1f	Spring cleaning (CEOI20_cleaning)	C++20	17 / 100	123 ms	70652 KiB

cleaning

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

#define int long long

const int MAX_SOM=100*1000+5,MAX_LOG=19;
int nbSom,nbReq,racine,numSuf,numEuler,nbPair,nbImp,rep,plusFeuil;
vector<int> adja[MAX_SOM];
int parcSuf[MAX_SOM];
bool dv[MAX_SOM],dv2[MAX_SOM]; 
int borneEuler[MAX_SOM][2]; //renum
int maxSuiv[3*MAX_SOM][MAX_LOG]; //renum
int euler[3*MAX_SOM]; //renum
int corresp[MAX_SOM]; //renum
int puis2Inf[3*MAX_SOM];
int anci[MAX_SOM];
int nbSurPair[MAX_SOM],nbSurImp[MAX_SOM];
vector<int> listeFils[MAX_SOM];
int nbFeuil,nbModif;
int feuilSous[MAX_SOM];
int pere[MAX_SOM];
set<int> somModif;
int nbNouv[MAX_SOM];

void DFS(int pos) {
    if (!dv[pos]) {
        dv[pos]=true;
        for (int i:adja[pos]) {
            DFS(i);
        }
        numSuf++;
        parcSuf[pos]=numSuf;
        corresp[numSuf]=pos;
    }
}

void DFS2(int pos,int anci)  {
    if (!dv2[pos]) {
        pere[pos]=anci;
        dv2[pos]=true;
        numEuler++;
        borneEuler[parcSuf[pos]][0]=numEuler;
        euler[numEuler]=parcSuf[pos];
        for (int i:adja[pos]) {
            if (!dv2[i]) {
                numEuler++;
                euler[numEuler]=parcSuf[pos];
                listeFils[pos].push_back(i);
                DFS2(i,pos);
            }
        }
        numEuler++;
        borneEuler[parcSuf[pos]][1]=numEuler;
        euler[numEuler]=parcSuf[pos];
    }
}
 
int lca(int som1,int som2) {
    int deb=min(borneEuler[som1][0],borneEuler[som2][0]),fin=max(borneEuler[som1][1],borneEuler[som2][1]);
    //cout<<deb<<" "<<fin<<" "<<puis2Inf[fin-deb]<<endl;
    return max(maxSuiv[deb][puis2Inf[fin-deb]],maxSuiv[fin-(1<<puis2Inf[fin-deb])+1][puis2Inf[fin-deb]]);
}

int calcFeuille(int pos) {
    if (adja[pos].size()==1) {
        feuilSous[pos]=1;
        nbFeuil++;
    }
    else {
        for (int i:listeFils[pos]) {
            feuilSous[pos]+=calcFeuille(i);
        }
    }
    return feuilSous[pos];
}

void calcDessus(int pos) {
    if (nbSurPair[pos]!=-1) {
        return;
    }
    calcDessus(pere[pos]);
    nbSurPair[pos]=nbSurPair[pere[pos]];
    nbSurImp[pos]=nbSurImp[pere[pos]];
    if (feuilSous[pos]%2==0) {
        nbSurPair[pos]++;
        nbPair++;
    }
    else {
        nbSurImp[pos]++;
        nbImp++;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbSom>>nbReq;   
    for (int i=0;i<nbSom-1;i++) {
        int debAre,finAre;
        cin>>debAre>>finAre;
        adja[debAre].push_back(finAre);
        adja[finAre].push_back(debAre);
    } 
    for (int i=1;i<=nbSom;i++) {
        if ((int)adja[i].size()>1) {
            racine=i;
        }
    }
    DFS(racine);
    DFS2(racine,racine);
    for (int i=0;i<3*nbSom;i++) {
        maxSuiv[i][0]=euler[i];
    }
    for (int j=1;j<MAX_LOG;j++) {
        for (int i=0;i<3*nbSom;i++) {
            maxSuiv[i][j]=max(maxSuiv[i][j-1],maxSuiv[min(i+(1<<(j-1)),3*MAX_SOM-1)][j-1]);
        }
    }
    puis2Inf[1]=0;
    for (int i=2;i<3*nbSom;i++) {
        puis2Inf[i]=puis2Inf[i/2]+1;
    }
    /*for (int i=1;i<3*nbSom;i++) {
        cout<<puis2Inf[i]<<" ";
    }
    cout<<endl;
    for (int i=1;i<3*nbSom;i++) {
        cout<<euler[i]<<" ";
    }
    cout<<endl;
    for (int i=1;i<=nbSom;i++) {
        cout<<i<<" : "<<parcSuf[i]<<endl;
    }
    for (int i=1;i<=nbSom;i++) {
        cout<<i<<" : "<<pere[i]<<endl;
    }
    cout<<endl;*/
    calcFeuille(racine);
    for (int i=1;i<=nbSom;i++) {
        nbSurPair[i]=-1;
        nbSurImp[i]=-1;
    }
    nbSurImp[racine]=0;
    nbSurPair[racine]=0;
    for (int i=1;i<=nbSom;i++) {
        calcDessus(i);
        //cout<<i<<" : "<<nbSurImp[i]<<" "<<nbSurPair[i]<<endl;
    }
    //cout<<nbImp<<" "<<nbPair<<" "<<nbFeuil<<endl;
    for (int ireq=0;ireq<nbReq;ireq++) {
        cin>>nbModif;
        somModif.clear();
        for (int i=0;i<nbModif;i++) {
            int nouv;
            cin>>nouv;
            somModif.insert(nouv);
            nbNouv[nouv]++;
        }
        plusFeuil=0;
        for (int i:somModif) {
            if (adja[i].size()==1) {
                plusFeuil++;
                nbNouv[i]--;
            }
        }
        if ((nbFeuil+nbModif-plusFeuil)%2==1) {
            cout<<-1<<"\n";
        }
        else {
            rep=nbImp+2*nbPair+nbModif; 
            for (int i:somModif) { //cas une modif
                rep+=nbNouv[i]*(nbSurImp[i]-nbSurPair[i]);
            }
            cout<<rep<<"\n";
        }
        for (int i:somModif) {
            nbNouv[i]=0;
        }
    }
}

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