Submission #1073671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073671		oscar1f	Werewolf (IOI18_werewolf)	C++17	0 / 100	4074 ms	51648 KiB

werewolf

#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<=0) {
            bloc[pos]=nbBlocs;
            listeBloc[nbBlocs].push_back(pos);
            pos++;
            tailleEnCours+=ajout[pos][0].size();
        }
    }
    /*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;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51