답안 #83671 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83671	2018-11-09T18:27:27 Z	AdrienVannson	늑대인간 (IOI18_werewolf)	C++17	100 / 100	1303 ms	135624 KB

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.0 / 7.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #83671

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 8.0 / 8.0

Subtask #3 34.0 / 34.0

Subtask #4 51.0 / 51.0

Subtask #1
7.0 / 7.0

Subtask #2
8.0 / 8.0

Subtask #3
34.0 / 34.0

Subtask #4
51.0 / 51.0