Submission #168331

#	Time	Username	Problem	Language	Result	Execution time	Memory
168331		Mounir	Werewolf (IOI18_werewolf)	C++14	0 / 100	530 ms	91084 KiB

werewolf

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

struct Requete {
	int noeudDep, noeudArrivee, borneMin, borneMax; //Données de l'entrée
	//noeudDep c'est humain noeudArrivee c'est loup-garou
	int iReq;
	int noeudPlus, noeudMoins;
	bool possible;
	
	bool operator < (const Requete &autre) const
	{
		return iReq < autre.iReq;
	}
};

const int BORNE = 2e5 + 1, BCP = ceil(log2(BORNE)), TREE = (1 << (BCP + 1));
vector<int> voisins[BORNE];
vector<int> enfantsPlus[BORNE], enfantsMoins[BORNE];
int dsu_ens[BORNE];
int profondeurPlus[BORNE], profondeurMoins[BORNE];
vector<int> ancetresPlus[BORNE], ancetresMoins[BORNE];
int ancetresDfs[BORNE];
int eulerTree[TREE];
int debPlus[BORNE], finPlus[BORNE], debMoins[BORNE], finMoins[BORNE];
vector<Requete> requetes[BORNE];
vector<Requete> sac;
int nNoeuds, nArcs, nReqs;

int dsu_find(int iNoeud){
	if (dsu_ens[iNoeud] == iNoeud)
		return iNoeud;
	dsu_ens[iNoeud] = dsu_find(dsu_ens[iNoeud]);
	return dsu_ens[iNoeud];
}

void dsu_union(int noeudPere, int noeudEnfant, bool estPlus){
	noeudPere = dsu_find(noeudPere), noeudEnfant = dsu_find(noeudEnfant);
	dsu_ens[noeudEnfant] = dsu_ens[noeudPere];
	
	if (estPlus)
		enfantsPlus[noeudPere].push_back(noeudEnfant);
	else
		enfantsMoins[noeudPere].push_back(noeudEnfant);
}

void faireDsu(){
	for (int iNoeud = 0; iNoeud < nNoeuds; ++iNoeud)
		dsu_ens[iNoeud] = iNoeud;
	//Le DSU plus : les trucs au-dessus.
	for (int iNoeud = nNoeuds - 1; iNoeud >= 0; --iNoeud){
		for (int voisin : voisins[iNoeud]){
			if (voisin > iNoeud)
				dsu_union(iNoeud, voisin, true);
		}
	}
	
	for (int iNoeud = 0; iNoeud < nNoeuds; ++iNoeud)
		dsu_ens[iNoeud] = iNoeud;
	for (int iNoeud = 0; iNoeud < nNoeuds; ++iNoeud){
		for (int voisin : voisins[iNoeud]){
			if (voisin < iNoeud)
				dsu_union(iNoeud, voisin, false);
		}
	}
}

void buildBinaryPlus(int iNoeud, int profCur){
	profondeurPlus[iNoeud] = profCur;
	ancetresDfs[profCur] = iNoeud;
	for (int delta = 1; profCur >= delta; delta *= 2)
		ancetresPlus[iNoeud].push_back(ancetresDfs[profCur - delta]);
	for (int enfant : enfantsPlus[iNoeud])
		buildBinaryPlus(enfant, profCur + 1);
}

void buildBinaryMoins(int iNoeud, int profCur){
	profondeurMoins[iNoeud] = profCur;
	ancetresDfs[profCur] = iNoeud;
	for (int delta = 1; profCur >= delta; delta *= 2)
		ancetresMoins[iNoeud].push_back(ancetresDfs[profCur - delta]);
	for (int enfant : enfantsMoins[iNoeud])
		buildBinaryMoins(enfant, profCur + 1);
}

int trouveRacinePlus(int noeudDep, int borneMax){
	//Sorte de dichotomie sur l'arbre.
	//Un père est supérieur à ses enfants.
	int iAncetre = ancetresPlus[noeudDep].size() - 1;
	for (;iAncetre >= 0;--iAncetre){
		if ((int)ancetresPlus[noeudDep].size() > iAncetre){
			int noeudTest = ancetresPlus[noeudDep][iAncetre];
			if (noeudTest <= borneMax)
				noeudDep = noeudTest;
		}
	}
	return noeudDep;
}

int trouveRacineMoins(int noeudDep, int borneMin){
	//Ici un père est inférieur à ses enfants.
	int iAncetre = ancetresMoins[noeudDep].size() - 1;
	for (; iAncetre >= 0; --iAncetre){
		if ((int)ancetresMoins[noeudDep].size() > iAncetre){
			int noeudTest = ancetresMoins[noeudDep][iAncetre];
			if (noeudTest >= borneMin)
				noeudDep = noeudTest;
		}
	}
	return noeudDep;
}

int temps = 0;
void tourEulerienPlus(int iNoeud){
	debPlus[iNoeud] = temps++;
	for (int enfant : enfantsPlus[iNoeud])
		tourEulerienPlus(enfant);
	finPlus[iNoeud] = temps++;
}

void prepareTree(){
	for (int iNoeud = 0; iNoeud < TREE; ++iNoeud)
		eulerTree[iNoeud] = 0;
}

void updateTree(int iNoeud){
	eulerTree[iNoeud]++;
	iNoeud /= 2;
	for (;iNoeud > 0; iNoeud /= 2)
		eulerTree[iNoeud] = eulerTree[iNoeud * 2] + eulerTree[iNoeud * 2 +1];
}

bool reqTree(int gauche, int droite){
	if (droite < gauche)
		return false;
	if (gauche%2 == 1)
		return ((eulerTree[gauche] > 0) || reqTree(gauche + 1, droite));
	if (droite%2 == 0)
		return ((eulerTree[droite] > 0) || reqTree(gauche, droite - 1));
	return reqTree(gauche/2, droite/2);
}

void makeDfs(int iNoeud){
	for (int enfant : enfantsMoins[iNoeud])
		makeDfs(enfant);
	updateTree(debPlus[iNoeud] + TREE/2);
	for (Requete requete : requetes[iNoeud]){
		requete.possible = reqTree(TREE/2 + debPlus[iNoeud], TREE/2 + finPlus[iNoeud]);
	}
}

void updReq(){
	for (Requete& req : sac){
		req.noeudPlus = trouveRacinePlus(req.noeudArrivee, req.borneMax);
		req.noeudMoins = trouveRacineMoins(req.noeudDep, req.borneMin);
		requetes[req.noeudMoins].push_back(req);
	}
}

vector<int> resoud(){
	faireDsu();
	buildBinaryMoins(0, 0); //La racine de moins est 0
	buildBinaryPlus(nNoeuds - 1, 0);
	updReq();
	tourEulerienPlus(nNoeuds - 1);
	prepareTree();
	makeDfs(0);
	vector<int> answers;
	vector<Requete> solReq;
	for (int iNoeud = 0; iNoeud < nNoeuds; ++iNoeud){
		for (Requete req : requetes[iNoeud])
			solReq.push_back(req);
	}
	sort(solReq.begin(), solReq.end());
	for (Requete req : solReq)
		answers.push_back(req.possible);
	return answers;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
	nNoeuds = N;
	nArcs = X.size();
	for (int iArc = 0; iArc < nArcs; ++iArc){
		voisins[X[iArc]].push_back(Y[iArc]);
		voisins[Y[iArc]].push_back(X[iArc]);
	}
	nReqs = S.size();
	for (int iReq = 0; iReq < nReqs; ++iReq){
		int i = iReq;
		Requete reqCur= {S[i], E[i], L[i], R[i], iReq, -1, -1, false};
		sac.push_back(reqCur);
	}
	return resoud();
}

Compilation message (stderr)

werewolf.cpp: In function 'void makeDfs(int)':
werewolf.cpp:147:15: warning: variable 'requete' set but not used [-Wunused-but-set-variable]
  for (Requete requete : requetes[iNoeud]){
               ^~~~~~~

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