Submission #1235254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235254		oscar1f	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	389 ms	84240 KiB

cleaning

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

#define int long long

const int MAX_SOM=100*1000+5,MAX_LOG=19,DECA=(1<<17);
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];
int debSous[MAX_SOM]; //renum
unordered_map<int,int> arb[2];

void DFS(int pos) {
    if (!dv[pos]) {
        dv[pos]=true;
        int deb=numSuf+1;
        for (int i:adja[pos]) {
            DFS(i);
        }
        numSuf++;
        parcSuf[pos]=numSuf;
        debSous[numSuf]=deb;
        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++;
    }
}

void ajout(int pos,int val,int id) {
    pos+=DECA;
    while (pos>0) {
        arb[id][pos]+=val;
        pos/=2;
    }
}

int calcSom(int deb,int fin,int id) {
    if (deb==fin) {
        return arb[id][deb];
    }
    if (deb%2==1) {
        return arb[id][deb]+calcSom(deb+1,fin,id);
    }
    if (fin%2==0) {
        return arb[id][fin]+calcSom(deb,fin-1,id);
    }
    return calcSom(deb/2,fin/2,id);
}

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;
    for (int i=1;i<=nbSom;i++) {
        cout<<i<<" : "<<parcSuf[i]<<" "<<debSous[parcSuf[i]]<<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; 
            //cout<<"?"<<rep<<endl;
            vector<int> somAj;
            arb[0].clear();
            arb[1].clear();
            for (int i:somModif) {
                if (nbNouv[i]%2==1) {
                    somAj.push_back(parcSuf[i]);
                    ajout(parcSuf[i],1,0);
                }
            }
            sort(somAj.begin(),somAj.end());
            set<int> listeLCA;
            for (int i:somAj) {
                listeLCA.insert(i);
            }
            for (int i=0;i<(int)somAj.size()-1;i++) {
                listeLCA.insert(lca(somAj[i],somAj[i+1]));
            }
            for (int i:listeLCA) {
                int obj=calcSom(DECA+debSous[i],DECA+i,0)%2;
                int dejaFait=calcSom(DECA+debSous[i],DECA+i,1);
                //cout<<i<<" : "<<obj<<" "<<dejaFait<<" "<<nbSurImp[i]<<" "<<nbSurPair[i]<<endl;
                rep+=(obj-dejaFait)*(nbSurImp[corresp[i]]-nbSurPair[corresp[i]]);
                ajout(i,obj-dejaFait,1);
            }
            /*for (int i=1;i<=nbSom;i++) {
                int obj=calcSom(DECA+debSous[i],DECA+i,0)%2;
                int dejaFait=calcSom(DECA+debSous[i],DECA+i,1);
                rep+=(obj-dejaFait)*(nbSurImp[corresp[i]]-nbSurPair[corresp[i]]);
                ajout(i,obj-dejaFait,1);
                //cout<<corresp[i]<<" "<<obj<<" "<<dejaFait<<" "<<nbSurImp[corresp[i]]<<" "<<nbSurPair[corresp[i]]<<endl;
            }*/
            cout<<rep<<"\n";
        }
        for (int i:somModif) {
            nbNouv[i]=0;
        }
    }
}

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