Submission #83671

#	Time	Username	Problem	Language	Result	Execution time	Memory
83671		AdrienVannson	Werewolf (IOI18_werewolf)	C++17	100 / 100	1303 ms	135624 KiB

werewolf

#include <bits/stdc++.h>

#include "werewolf.h"

using namespace std;

template<int NB_NOEUDS>
class UnionFind
{
public:

    UnionFind ()
    {
        for (int iNoeud=0; iNoeud<NB_NOEUDS; iNoeud++) {
            representants[iNoeud] = iNoeud;
            tailles[iNoeud] = 1;
        }
    }

    int representant (const int iNoeud)
    {
        if (representants[iNoeud] == iNoeud) {
            return iNoeud;
        }
        return representants[iNoeud] = representant(representants[iNoeud]);
    }

    int taille (const int iNoeud)
    {
        return tailles[representant(iNoeud)];
    }

    void unir (int iNoeud1, int iNoeud2)
    {
        iNoeud1 = representant(iNoeud1);
        iNoeud2 = representant(iNoeud2);

        if (iNoeud1 == iNoeud2) {
            return;
        }

        tailles[iNoeud1] += tailles[iNoeud2];
        tailles[iNoeud2] = 0;

        representants[iNoeud2] = iNoeud1;
    }

private:
    int representants[NB_NOEUDS];
    int tailles[NB_NOEUDS]; // Valide uniquement pour les racines
};

const int NB_FORMES = 2;

const int FORME_HUMAINE = 0;
const int FORME_LOUP = 1;

const int NB_MAX_NOEUDS = 200*1000;


struct Noeud
{
    vector<int> voisins;
};

int nbNoeuds;
Noeud noeuds[NB_MAX_NOEUDS];


/*
 * Arbres
 */

struct NoeudArbre
{
    int parents[22];
    vector<int> enfants;
    int debut, fin;

    NoeudArbre () :
        debut(-1), fin(-1)
    {
        fill(parents, parents+22, -1);
    }
};

UnionFind<NB_MAX_NOEUDS> unionfind;
NoeudArbre arbres[NB_FORMES][NB_MAX_NOEUDS];

void genererArbre (const int forme)
{
    unionfind = UnionFind<NB_MAX_NOEUDS> ();

    for (int iIteration=0; iIteration<nbNoeuds; iIteration++) {

        const int iNoeud = forme == FORME_LOUP ? iIteration : nbNoeuds-iIteration-1;
        const Noeud &noeud = noeuds[iNoeud];

        for (int iVoisin : noeud.voisins) {

            // Si le voisin est déjà dans l'arbre
            if ((forme == FORME_LOUP && iVoisin < iNoeud) || (forme == FORME_HUMAINE && iVoisin > iNoeud)) {
                if (unionfind.representant(iNoeud) != unionfind.representant(iVoisin)) {
                    arbres[forme][iNoeud].enfants.push_back( unionfind.representant(iVoisin) );
                    arbres[forme][unionfind.representant(iVoisin)].parents[0] = iNoeud;
                    unionfind.unir(iNoeud, iVoisin);
                }
            }
        }
    }
}

int calculerIntervalles (const int iNoeud, const int forme) // --> nbDescendants (noeud actuel inclus)
{
    NoeudArbre &noeud = arbres[forme][iNoeud];

    int nbDescendants = 1;

    for (int enfant : noeud.enfants) {
        arbres[forme][enfant].debut = noeud.debut + nbDescendants;
        nbDescendants += calculerIntervalles(enfant, forme);
    }

    noeud.fin = noeud.debut + nbDescendants;

    return nbDescendants;
}

// Lors de l'appel, les parents des parents du noeud sont déjà à jour
void calculerParents (const int iNoeud, const int forme)
{
    NoeudArbre &noeud = arbres[forme][iNoeud];

    for (int iEtape=1; noeud.parents[iEtape-1] != -1; iEtape++) {
        noeud.parents[iEtape] = arbres[forme][ noeud.parents[iEtape-1] ].parents[iEtape-1];
    }
}


/*
 * Arbre binaire
 */

struct ArbreBinaire
{
    static const int PROFONDEUR = 18;
    static const int PREMIERE_FEUILLE = 1<<PROFONDEUR;
    static const int NB_NOEUDS = 2*PREMIERE_FEUILLE;

    ArbreBinaire ()
    {
        fill(noeuds, noeuds+NB_NOEUDS, 0);
    }

    void incrementer (const int pos)
    {
        int iNoeud = PREMIERE_FEUILLE + pos;

        while (iNoeud >= 1) {
            noeuds[iNoeud]++;
            iNoeud /= 2;
        }
    }

    int getSomme (const int debut, const int fin,
                  const int iNoeudActuel=1, const int debutActuel=0, const int finActuelle=PREMIERE_FEUILLE)
    {
        if (debutActuel >= debut && finActuelle <= fin) {
            return noeuds[iNoeudActuel];
        }
        if (finActuelle <= debut || debutActuel >= fin) {
            return 0;
        }

        const int milieuActuel = (debutActuel+finActuelle) / 2;

        return getSomme(debut, fin, iNoeudActuel*2, debutActuel, milieuActuel)
             + getSomme(debut, fin, iNoeudActuel*2+1, milieuActuel, finActuelle);
    }

    int noeuds[NB_NOEUDS];
};

ArbreBinaire arbreBinaire;


/*
 * Balayage
 */

struct Evenement
{
    int date;
    bool estIntervalle;

    int debut, fin;
    int iRequete;

    bool operator< (const Evenement &autre) const
    {
        if (date != autre.date) {
            return date < autre.date;
        }
        if (estIntervalle != autre.estIntervalle) {
            return estIntervalle; // TODO: vérifier
        }
        if (debut != autre.debut) {
            return debut < autre.debut;
        }
        if (fin != autre.fin) {
            return fin < autre.fin;
        }
        return iRequete < autre.iRequete;
    }
};

int getRacineAccessible (const int forme, const int iNoeud, const int seuil)
{
    int iEtape = 21;

    while (iEtape >= 0 &&
               (arbres[forme][iNoeud].parents[iEtape] == -1
            || (forme == FORME_HUMAINE ? arbres[forme][iNoeud].parents[iEtape] < seuil : arbres[forme][iNoeud].parents[iEtape] > seuil))) {
        iEtape--;
    }

    if (iEtape == -1) {
        return iNoeud;
    }
    return getRacineAccessible(forme, arbres[forme][iNoeud].parents[iEtape], seuil);
}


vector<int> check_validity (int nbNoeuds_, vector<int> noeuds1Arretes, vector<int> noeuds2Arretes,
                            vector<int> villesDeparts, vector<int> villesArrivees,
                            vector<int> seuilsBas, vector<int> seuilsHauts )
{
    nbNoeuds = nbNoeuds_;
    for (int iArrete=0; iArrete<(int)noeuds1Arretes.size(); iArrete++) {
        noeuds[noeuds1Arretes[iArrete]].voisins.push_back(noeuds2Arretes[iArrete]);
        noeuds[noeuds2Arretes[iArrete]].voisins.push_back(noeuds1Arretes[iArrete]);
    }
    const int nbRequetes = villesDeparts.size();

    genererArbre(FORME_HUMAINE);
    genererArbre(FORME_LOUP);


    int debutActuel = 0;
    for (int iNoeud=0; iNoeud<nbNoeuds; iNoeud++) {
        if (arbres[FORME_HUMAINE][iNoeud].fin == -1) {
            arbres[FORME_HUMAINE][iNoeud].debut = debutActuel;
            debutActuel += calculerIntervalles(iNoeud, FORME_HUMAINE);
        }
        calculerParents(iNoeud, FORME_HUMAINE);
    }

    debutActuel = 0;
    for (int iNoeud=nbNoeuds-1; iNoeud>=0; iNoeud--) {
        if (arbres[FORME_LOUP][iNoeud].fin == -1) {
            arbres[FORME_LOUP][iNoeud].debut = debutActuel;
            debutActuel += calculerIntervalles(iNoeud, FORME_LOUP);
        }
        calculerParents(iNoeud, FORME_LOUP);
    }

#if 0
    cerr << "Forme " << FORME_LOUP << endl;
    for (int i=0; i<nbNoeuds; i++) {
        cerr << i << ": " << arbres[FORME_LOUP][i].debut << " " << arbres[FORME_LOUP][i].fin << endl;
        /*for (int e : arbres[FORME_LOUP][i].enfants) {
            cerr << e << " ";
        }
        cerr << endl;*/
    }
#endif

    vector<Evenement> evenements;

    for (int iNoeud=0; iNoeud<nbNoeuds; iNoeud++) {
        const int pos1 = arbres[FORME_HUMAINE][iNoeud].debut;
        const int pos2 = arbres[FORME_LOUP][iNoeud].debut;

        evenements.push_back(Evenement{pos1, false, pos2, -1, -1});
    }

    for (int iRequete=0; iRequete<nbRequetes; iRequete++) {
        const int iNoeud1 = getRacineAccessible(FORME_HUMAINE, villesDeparts[iRequete], seuilsBas[iRequete]);
        const int iNoeud2 = getRacineAccessible(FORME_LOUP, villesArrivees[iRequete], seuilsHauts[iRequete]);

        const int debut1 = arbres[FORME_HUMAINE][iNoeud1].debut;
        const int fin1 = arbres[FORME_HUMAINE][iNoeud1].fin;

        const int debut2 = arbres[FORME_LOUP][iNoeud2].debut;
        const int fin2 = arbres[FORME_LOUP][iNoeud2].fin;

        evenements.push_back(Evenement{debut1, true, debut2, fin2, iRequete});
        evenements.push_back(Evenement{fin1, true, debut2, fin2, iRequete});
    }

    sort(evenements.begin(), evenements.end());

    vector<int> nbAvants (nbRequetes);
    fill(nbAvants.begin(), nbAvants.end(), -1);

    for (const Evenement &evenement : evenements) {
        if (evenement.estIntervalle) {
            const int iRequete = evenement.iRequete;

            if (nbAvants[iRequete] == -1) {
                nbAvants[iRequete] = arbreBinaire.getSomme(evenement.debut, evenement.fin);
            }
            else {
                nbAvants[iRequete] = arbreBinaire.getSomme(evenement.debut, evenement.fin) - nbAvants[iRequete];
            }
        }
        else { // Mise à jour
            arbreBinaire.incrementer(evenement.debut);
        }
    }

    for (int iRequete=0; iRequete<nbRequetes; iRequete++) {
        nbAvants[iRequete] = nbAvants[iRequete] > 0;
    }

    return nbAvants;
}

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