#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int MAX_SOM=200*1000+5;
int nbSom,nbAre,nbBlocs,nbReq;
vector<int> rep;
int bloc[MAX_SOM];
vector<int> listeBloc[MAX_SOM];
vector<pair<int,int>> ajout[MAX_SOM][2];
int pere[2*MAX_SOM],prof[2*MAX_SOM];
vector<pair<int,int>> modifProf,modifPere;
vector<tuple<int,int,int,int,int>> reqBloc[MAX_SOM];
int find(int pos) {
while (pos!=pere[pos]) {
pos=pere[pos];
}
return pos;
}
void unir(int deb,int fin,int supp) {
deb=find(deb);
fin=find(fin);
if (deb!=fin) {
if (prof[deb]>prof[fin]) {
swap(deb,fin);
}
if (supp==1) {
modifPere.push_back({deb,pere[deb]});
modifProf.push_back({fin,prof[fin]});
}
prof[fin]=max(prof[fin],prof[deb]+1);
pere[deb]=fin;
}
}
void init() {
for (int i=0;i<2*nbSom;i++) {
pere[i]=i;
prof[i]=1;
}
for (int i=0;i<nbSom;i++) {
unir(i,i+nbSom,0);
}
}
void ajoutAre(int pos,int tab,int supp) {
for (auto i:ajout[pos][tab]) {
unir(i.first,i.second,supp);
}
}
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R) {
nbSom=N;
nbAre=X.size();
nbReq=S.size();
rep.resize(nbReq);
int debAre,finAre;
for (int i=0;i<nbSom;i++) {
debAre=min(X[i],Y[i]);
finAre=max(X[i],Y[i]);
ajout[debAre][0].push_back({debAre,finAre});
ajout[finAre][1].push_back({finAre+nbSom,debAre+nbSom});
}
int tailleEnCours,pos=0;
while (pos<nbSom) {
nbBlocs++;
tailleEnCours=0;
while (pos<nbSom and tailleEnCours<=sqrt(nbAre)) {
bloc[pos]=nbBlocs;
listeBloc[nbBlocs].push_back(pos);
pos++;
tailleEnCours+=ajout[pos][0].size()+2*nbAre;
}
}
/*for (int i=1;i<=nbBlocs;i++) {
for (int j:listeBloc[i]) {
cout<<j<<" ";
}
cout<<endl;
}*/
for (int i=0;i<nbReq;i++) {
reqBloc[bloc[L[i]]].push_back({R[i],L[i],S[i],E[i],i});
}
int maxLoup,minHom,somDeb,somFin,dernLoup,idReq;
for (int iBloc=nbBlocs;iBloc>0;iBloc--) {
init();
sort(reqBloc[iBloc].begin(),reqBloc[iBloc].end());
for (int i=listeBloc[iBloc].back();i<nbSom;i++) {
ajoutAre(i,0,0);
}
dernLoup=-1;
for (auto j:reqBloc[iBloc]) {
maxLoup=get<0>(j);
minHom=get<1>(j);
somDeb=get<2>(j);
somFin=get<3>(j);
idReq=get<4>(j);
for (int i=dernLoup+1;i<=maxLoup;i++) {
ajoutAre(i,1,0);
}
modifPere.clear();
modifProf.clear();
for (int i=listeBloc[iBloc].back()-1;i>=minHom;i--) {
ajoutAre(i,0,1);
}
if (find(somDeb)==find(somFin+nbSom)) {
rep[idReq]=1;
}
while (!modifPere.empty()) {
pere[modifPere.back().first]=modifPere.back().second;
modifPere.pop_back();
}
while (!modifProf.empty()) {
prof[modifProf.back().first]=modifProf.back().second;
modifProf.pop_back();
}
}
}
return rep;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
22364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
22364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4030 ms |
53328 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
22364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
