| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 168330 | Mounir | 늑대인간 (IOI18_werewolf) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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> anwers;
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){
Requete reqCur= {S[i], E[i], L[i], R[i], iReq, -1, -1, false};
sac.push_back(reqCur);
}
return resoud();
}