Submission #108153

#	Time	Username	Problem	Language	Result	Execution time	Memory
108153		hugo_pm	Werewolf (IOI18_werewolf)	C++17	15 / 100	4091 ms	100496 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vecInt;

// Version classique du segment tree
// Opérations en O(log N)
// Indices 0-indexés

class SegtreeClassic
{
    public:
        void init(vector<int> tab);
        int requete(int gauche, int droite);
        void modifier(int index, int val);

    private:
        const int UNDEF = 1e9 + 171;
        int nbElements;
        int combiner(int a, int b);
        vector<int> interne;
};

void SegtreeClassic::init(vector<int> tab)
{
    nbElements = tab.size();
    interne.resize(2 * nbElements);

    for (int ind = 0; ind < nbElements; ++ind)
        interne[ind + nbElements] = tab[ind];

    for (int ind = nbElements - 1; ind >= 0; --ind)
        interne[ind] = combiner(interne[2*ind], interne[2*ind + 1]);
}

int SegtreeClassic::requete(int gauche, int droite)
{
    int res = UNDEF;
    ++droite; // Pour passer à un intervalle semi-ouvert [l ; r[
    gauche += nbElements;
    droite += nbElements;

    while (gauche < droite)
    {
        // Si gauche est impair, le noeud est inclus mais pas le parent
        // On ajoute donc ce noeud et on passera plus tard au noeud à droite du parent
        if (gauche & 1)
            res = combiner(res, interne[gauche++]);
        // Même raisonnement sachant que droite est exclus, d'où la {pré}-décrémentation
        if (droite & 1)
            res = combiner(res, interne[--droite]);
        
        gauche /= 2;
        droite /= 2;
    }

    return res;
}

void SegtreeClassic::modifier(int index, int val)
{
    index += nbElements;
    interne[index] = val;
    index /= 2;
    while (index > 0)
    {
        interne[index] = combiner(interne[2*index], interne[2*index+1]);
        index /= 2;
    }
}

int SegtreeClassic::combiner(int a, int b)
{
    if (a == UNDEF) return b;
    if (b == UNDEF) return a;
    return a+b;
}

const int borne = 201*1000;

// DSU
int repr[borne];

void initDsu()
{
	form(i, borne) repr[i] = i;
}

int trouver(int x)
{
	if (repr[x] != x) repr[x] = trouver(repr[x]);
	return repr[x];
}

// Fin

int nbNoeuds, nbAretes, nbRequetes;
vecInt adj[borne];

vector<vecInt> arbreHumain;
vector<vecInt> arbreLoup;
vecInt seqHum, seqLoup;
vecInt parHum, parLoup;
vector<pii> tempsHum, tempsLoup;
vector<int> rep, tw;

SegtreeClassic sc;

struct Trio
{
	int xMin, xMax, ind;
};

vector<Trio> evAdd[2*borne], evRem[2*borne];
vecInt addPoint[2*borne];

void buildSeq(vector<vecInt> &arbre, vecInt &seq, vector<pii> &temps, int nod, int par)
{
	temps[nod].fi = seq.size();
	seq.push_back(nod);
	for (int vo : arbre[nod]) if (vo != par) {
		buildSeq(arbre, seq, temps, vo, nod);
	}
	temps[nod].se = seq.size();
	seq.push_back(nod);
}

void balayage()
{
	form(y, 2*borne) {
		for (Trio cc : evAdd[y]) {
			int cur = sc.requete(cc.xMin, cc.xMax);
			tw[cc.ind] = cur;
		}
		for (int x : addPoint[y]) {
			int ov = sc.requete(x, x);
			sc.modifier(x,ov+1);
		}
		for (Trio cc : evRem[y]) {
			int cur = sc.requete(cc.xMin, cc.xMax);
			if (cur > tw[cc.ind]) rep[cc.ind] = 1;
		}
	}
}

void traiter(int ind, int dep, int arr, int minHum, int maxLoup)
{
	int subHum = dep;
	int subLoup = arr;

	while (parHum[subHum] != -1 && parHum[subHum] >= minHum) { subHum = parHum[subHum]; }

	while (parLoup[subLoup] != -1 && parLoup[subLoup] <= maxLoup) { subLoup = parLoup[subLoup]; }

	int y1 = tempsLoup[subLoup].fi;
	int y2 = tempsLoup[subLoup].se;

	evAdd[y1].push_back({tempsHum[subHum].fi, tempsHum[subHum].se, ind});

	evRem[y2].push_back({tempsHum[subHum].fi, tempsHum[subHum].se, ind});
}

vecInt check_validity(int N, vecInt X, vecInt Y, vecInt S, vecInt E, vecInt L, vecInt R)
{

	nbNoeuds = N;
	nbAretes = X.size();
	nbRequetes = S.size();
	vecInt A(nbRequetes);

	arbreHumain.resize(N);
	arbreLoup.resize(N);
	parHum.resize(N);
	parLoup.resize(N);
	tempsHum.resize(N);
	tempsLoup.resize(N);

	rep.resize(nbRequetes);
	tw.assign(nbRequetes, -1);

	sc.init(vector<int>(2*borne, 0));

	form(i, nbAretes) {
		int u = X[i], v = Y[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	initDsu();

	// Construire l'arbre humain (dans lequel les ensembles accessibles avec >= L[i] sont des sous-arbres)
	ford(noeud, nbNoeuds) {
		for (int voisin : adj[noeud]) if (voisin > noeud) {
			voisin = trouver(voisin);
			if (noeud != voisin) {
				repr[voisin] = noeud;
				arbreHumain[voisin].push_back(noeud);
				arbreHumain[noeud].push_back(voisin);
				parHum[voisin] = noeud;
			}	
		}
	}

	initDsu();

	// Construire l'arbre loup
	form(noeud, nbNoeuds) {
		for (int voisin : adj[noeud]) if (voisin < noeud) {
			voisin = trouver(voisin);
			if (noeud != voisin) {
				repr[voisin] = noeud;
				arbreLoup[voisin].push_back(noeud);
				arbreLoup[noeud].push_back(voisin);
				parLoup[voisin] = noeud;
			}
		}
	}

	parHum[0] = -1;
	parLoup[nbNoeuds-1] = -1;

	buildSeq(arbreHumain, seqHum, tempsHum, 0, -1);
	buildSeq(arbreLoup, seqLoup, tempsLoup, nbNoeuds-1, -1);

	form(nod, nbNoeuds) {
		int x = tempsHum[nod].fi, y = tempsLoup[nod].fi;
		addPoint[y].push_back(x);
	}

	form(i, nbRequetes) {
		traiter(i, S[i], E[i], L[i], R[i]);
	}
	balayage();
	return rep;
}

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