Submission #1235101

#TimeUsernameProblemLanguageResultExecution timeMemory
1235101oscar1fSpring cleaning (CEOI20_cleaning)C++20
0 / 100
79 ms61764 KiB
#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[i+(1<<(j-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; }*/ 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; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...