oj.uz

Submission #83671

# Submission time Handle Problem Language Result Execution time Memory
83671 2018-11-09T18:27:27 Z AdrienVannson Werewolf (IOI18_werewolf) C++17
100 / 100
 1303 ms 135624 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 57208 KB Output is correct
2 Correct 55 ms 57212 KB Output is correct
3 Correct 55 ms 57292 KB Output is correct
4 Correct 54 ms 57360 KB Output is correct
5 Correct 54 ms 57400 KB Output is correct
6 Correct 60 ms 57404 KB Output is correct
7 Correct 54 ms 57496 KB Output is correct
8 Correct 54 ms 57496 KB Output is correct
9 Correct 55 ms 57496 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 57208 KB Output is correct
2 Correct 55 ms 57212 KB Output is correct
3 Correct 55 ms 57292 KB Output is correct
4 Correct 54 ms 57360 KB Output is correct
5 Correct 54 ms 57400 KB Output is correct
6 Correct 60 ms 57404 KB Output is correct
7 Correct 54 ms 57496 KB Output is correct
8 Correct 54 ms 57496 KB Output is correct
9 Correct 55 ms 57496 KB Output is correct
10 Correct 65 ms 58316 KB Output is correct
11 Correct 62 ms 58380 KB Output is correct
12 Correct 63 ms 58576 KB Output is correct
13 Correct 63 ms 58708 KB Output is correct
14 Correct 63 ms 58832 KB Output is correct
15 Correct 66 ms 59192 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 898 ms 106320 KB Output is correct
2 Correct 1090 ms 115956 KB Output is correct
3 Correct 986 ms 115956 KB Output is correct
4 Correct 954 ms 115956 KB Output is correct
5 Correct 934 ms 115956 KB Output is correct
6 Correct 979 ms 115956 KB Output is correct
7 Correct 937 ms 115956 KB Output is correct
8 Correct 1058 ms 115956 KB Output is correct
9 Correct 809 ms 115956 KB Output is correct
10 Correct 721 ms 115956 KB Output is correct
11 Correct 771 ms 115956 KB Output is correct
12 Correct 811 ms 115956 KB Output is correct
13 Correct 1169 ms 122540 KB Output is correct
14 Correct 1094 ms 122540 KB Output is correct
15 Correct 1149 ms 122628 KB Output is correct
16 Correct 1164 ms 122644 KB Output is correct
17 Correct 934 ms 122644 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 57208 KB Output is correct
2 Correct 55 ms 57212 KB Output is correct
3 Correct 55 ms 57292 KB Output is correct
4 Correct 54 ms 57360 KB Output is correct
5 Correct 54 ms 57400 KB Output is correct
6 Correct 60 ms 57404 KB Output is correct
7 Correct 54 ms 57496 KB Output is correct
8 Correct 54 ms 57496 KB Output is correct
9 Correct 55 ms 57496 KB Output is correct
10 Correct 65 ms 58316 KB Output is correct
11 Correct 62 ms 58380 KB Output is correct
12 Correct 63 ms 58576 KB Output is correct
13 Correct 63 ms 58708 KB Output is correct
14 Correct 63 ms 58832 KB Output is correct
15 Correct 66 ms 59192 KB Output is correct
16 Correct 898 ms 106320 KB Output is correct
17 Correct 1090 ms 115956 KB Output is correct
18 Correct 986 ms 115956 KB Output is correct
19 Correct 954 ms 115956 KB Output is correct
20 Correct 934 ms 115956 KB Output is correct
21 Correct 979 ms 115956 KB Output is correct
22 Correct 937 ms 115956 KB Output is correct
23 Correct 1058 ms 115956 KB Output is correct
24 Correct 809 ms 115956 KB Output is correct
25 Correct 721 ms 115956 KB Output is correct
26 Correct 771 ms 115956 KB Output is correct
27 Correct 811 ms 115956 KB Output is correct
28 Correct 1169 ms 122540 KB Output is correct
29 Correct 1094 ms 122540 KB Output is correct
30 Correct 1149 ms 122628 KB Output is correct
31 Correct 1164 ms 122644 KB Output is correct
32 Correct 934 ms 122644 KB Output is correct
33 Correct 1100 ms 122644 KB Output is correct
34 Correct 580 ms 122644 KB Output is correct
35 Correct 1108 ms 122644 KB Output is correct
36 Correct 993 ms 122644 KB Output is correct
37 Correct 1089 ms 122644 KB Output is correct
38 Correct 1052 ms 122644 KB Output is correct
39 Correct 996 ms 133164 KB Output is correct
40 Correct 1303 ms 133164 KB Output is correct
41 Correct 1016 ms 133164 KB Output is correct
42 Correct 810 ms 133164 KB Output is correct
43 Correct 1167 ms 133164 KB Output is correct
44 Correct 1025 ms 133164 KB Output is correct
45 Correct 915 ms 133376 KB Output is correct
46 Correct 929 ms 133376 KB Output is correct
47 Correct 1184 ms 133376 KB Output is correct
48 Correct 1105 ms 133376 KB Output is correct
49 Correct 1151 ms 135560 KB Output is correct
50 Correct 1221 ms 135624 KB Output is correct
51 Correct 1248 ms 135624 KB Output is correct
52 Correct 1181 ms 135624 KB Output is correct