#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> ev[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 (int x : addPoint[y]) {
int ov = sc.requete(x, x);
sc.modifier(x,ov+1);
}
for (Trio cc : ev[y]) {
int cur = sc.requete(cc.xMin, cc.xMax);
if (tw[cc.ind] == -1) {
tw[cc.ind] = cur;
} else {
assert(cur >= tw[cc.ind]);
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;
ev[y1].push_back({tempsHum[subHum].fi, tempsHum[subHum].se, ind});
ev[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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
28672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
28672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
997 ms |
91028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
28672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
