Submission #168556

#	Time	Username	Problem	Language	Result	Execution time	Memory
168556		Mounir	Werewolf (IOI18_werewolf)	C++14	0 / 100	483 ms	89040 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];
set<int> eulerTree;
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++;
}

bool reqTree(int gauche, int droite){
	auto it = eulerTree.lower_bound(gauche);
	if (it != eulerTree.end() && *it <= droite)
		return true;
	return false;
}

void makeDfs(int iNoeud){
	for (int enfant : enfantsMoins[iNoeud])
		makeDfs(enfant);
	eulerTree.insert(debPlus[iNoeud]);
	for (Requete requete : requetes[iNoeud]){
		requete.possible = reqTree(debPlus[iNoeud], 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);
	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:132: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