답안 #83672 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83672	2018-11-09T18:29:59 Z	AdrienVannson	늑대인간 (IOI18_werewolf)	C++17	100 / 100	1380 ms	119420 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;
        }
        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);
    }

    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	57 ms	57208 KB	Output is correct
2	Correct	68 ms	57404 KB	Output is correct
3	Correct	57 ms	57408 KB	Output is correct
4	Correct	58 ms	57408 KB	Output is correct
5	Correct	58 ms	57408 KB	Output is correct
6	Correct	57 ms	57408 KB	Output is correct
7	Correct	62 ms	57408 KB	Output is correct
8	Correct	67 ms	57408 KB	Output is correct
9	Correct	57 ms	57408 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	57208 KB	Output is correct
2	Correct	68 ms	57404 KB	Output is correct
3	Correct	57 ms	57408 KB	Output is correct
4	Correct	58 ms	57408 KB	Output is correct
5	Correct	58 ms	57408 KB	Output is correct
6	Correct	57 ms	57408 KB	Output is correct
7	Correct	62 ms	57408 KB	Output is correct
8	Correct	67 ms	57408 KB	Output is correct
9	Correct	57 ms	57408 KB	Output is correct
10	Correct	68 ms	58108 KB	Output is correct
11	Correct	68 ms	58124 KB	Output is correct
12	Correct	66 ms	58128 KB	Output is correct
13	Correct	64 ms	58224 KB	Output is correct
14	Correct	73 ms	58236 KB	Output is correct
15	Correct	80 ms	58256 KB	Output is correct

Subtask #3
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1000 ms	102208 KB	Output is correct
2	Correct	1240 ms	106348 KB	Output is correct
3	Correct	1008 ms	106348 KB	Output is correct
4	Correct	915 ms	106348 KB	Output is correct
5	Correct	941 ms	106348 KB	Output is correct
6	Correct	974 ms	106348 KB	Output is correct
7	Correct	877 ms	106348 KB	Output is correct
8	Correct	1051 ms	106684 KB	Output is correct
9	Correct	832 ms	106684 KB	Output is correct
10	Correct	723 ms	106684 KB	Output is correct
11	Correct	747 ms	106684 KB	Output is correct
12	Correct	790 ms	106684 KB	Output is correct
13	Correct	1202 ms	113516 KB	Output is correct
14	Correct	1241 ms	113516 KB	Output is correct
15	Correct	1167 ms	113516 KB	Output is correct
16	Correct	1193 ms	113540 KB	Output is correct
17	Correct	906 ms	113540 KB	Output is correct

Subtask #4
51.0 / 51.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	57208 KB	Output is correct
2	Correct	68 ms	57404 KB	Output is correct
3	Correct	57 ms	57408 KB	Output is correct
4	Correct	58 ms	57408 KB	Output is correct
5	Correct	58 ms	57408 KB	Output is correct
6	Correct	57 ms	57408 KB	Output is correct
7	Correct	62 ms	57408 KB	Output is correct
8	Correct	67 ms	57408 KB	Output is correct
9	Correct	57 ms	57408 KB	Output is correct
10	Correct	68 ms	58108 KB	Output is correct
11	Correct	68 ms	58124 KB	Output is correct
12	Correct	66 ms	58128 KB	Output is correct
13	Correct	64 ms	58224 KB	Output is correct
14	Correct	73 ms	58236 KB	Output is correct
15	Correct	80 ms	58256 KB	Output is correct
16	Correct	1000 ms	102208 KB	Output is correct
17	Correct	1240 ms	106348 KB	Output is correct
18	Correct	1008 ms	106348 KB	Output is correct
19	Correct	915 ms	106348 KB	Output is correct
20	Correct	941 ms	106348 KB	Output is correct
21	Correct	974 ms	106348 KB	Output is correct
22	Correct	877 ms	106348 KB	Output is correct
23	Correct	1051 ms	106684 KB	Output is correct
24	Correct	832 ms	106684 KB	Output is correct
25	Correct	723 ms	106684 KB	Output is correct
26	Correct	747 ms	106684 KB	Output is correct
27	Correct	790 ms	106684 KB	Output is correct
28	Correct	1202 ms	113516 KB	Output is correct
29	Correct	1241 ms	113516 KB	Output is correct
30	Correct	1167 ms	113516 KB	Output is correct
31	Correct	1193 ms	113540 KB	Output is correct
32	Correct	906 ms	113540 KB	Output is correct
33	Correct	1041 ms	113540 KB	Output is correct
34	Correct	561 ms	113540 KB	Output is correct
35	Correct	1195 ms	113540 KB	Output is correct
36	Correct	998 ms	113540 KB	Output is correct
37	Correct	1134 ms	113540 KB	Output is correct
38	Correct	1149 ms	113540 KB	Output is correct
39	Correct	1016 ms	119356 KB	Output is correct
40	Correct	1380 ms	119356 KB	Output is correct
41	Correct	1031 ms	119356 KB	Output is correct
42	Correct	844 ms	119356 KB	Output is correct
43	Correct	1253 ms	119356 KB	Output is correct
44	Correct	1076 ms	119356 KB	Output is correct
45	Correct	970 ms	119420 KB	Output is correct
46	Correct	956 ms	119420 KB	Output is correct
47	Correct	1164 ms	119420 KB	Output is correct
48	Correct	1189 ms	119420 KB	Output is correct
49	Correct	1203 ms	119420 KB	Output is correct
50	Correct	1218 ms	119420 KB	Output is correct
51	Correct	1181 ms	119420 KB	Output is correct
52	Correct	1210 ms	119420 KB	Output is correct

답안 #83672

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