Submission #394908

#	Time	Username	Problem	Language	Result	Execution time	Memory
394908		Mounir	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1205 ms	181520 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define chmax(x, v) x = max(x, v)
#define all(x) x.begin(), x.end()
using namespace std;

struct Req {
	int depart, arrivee;
	int borneInf, borneSup;

	int iReq;
};

struct Noeud {
	int id, fin;

	bool operator < (const Noeud &autre) const {
		return fin < autre.fin;
	}
};

struct toLook {
	int root, iReq;
};

const int N_NOEUDS = (1 << 19);
int nNoeuds, nAretes, nReqs;

vector<int> voisins[N_NOEUDS];
int ens[N_NOEUDS];

int getEns(int noeud){
	if (ens[noeud] != noeud)
		ens[noeud] = getEns(ens[noeud]);
	return ens[noeud];
}

void initEns(){
	for (int noeud = 0; noeud < nNoeuds; ++noeud)
		ens[noeud] = noeud;
}


vector<int> enfants[2][N_NOEUDS];
vector<int> ancetres[2][N_NOEUDS];
int parcours[N_NOEUDS];
int prof[2][N_NOEUDS];
int deb[2][N_NOEUDS], fin[2][N_NOEUDS];
int temps = 0;

void dfs(int tour, int noeud, int etage){
	prof[tour][noeud] = etage;
	deb[tour][noeud] = temps++;
	parcours[etage] = noeud;

	for (int delta = 1; delta <= etage; delta *= 2)
		ancetres[tour][noeud].pb(parcours[etage - delta]);
	for (int enfant : enfants[tour][noeud])
		dfs(tour, enfant, etage + 1);
	fin[tour][noeud] = temps++;
}

void afficher(){
	for (int i = 0; i < 2; ++i){
		cout << "-------------\n";
		for (int noeud = 0; noeud < nNoeuds; ++noeud){
			cout << "NOEUD " << noeud << endl;
			for (int enfant : enfants[i][noeud])
				cout << enfant << " ";
			cout << endl;
		}
	}
}

int debMax[N_NOEUDS * 2];

int getMax(int gauche, int droite){
	//cout << "GET MAx " << gauche << " " << droite << endl;

	if (droite < gauche) return -1;
	if (gauche%2 == 1) return max(debMax[gauche], getMax(gauche + 1, droite));
	if (droite%2 == 0) return max(debMax[droite], getMax(gauche, droite - 1));
	return getMax(gauche/2, droite/2);
}

void update(int noeud, int val){
	for (; noeud > 0; noeud /= 2)
		chmax(debMax[noeud], val);
}

vector<toLook> aRegarder[N_NOEUDS];

vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  

	nNoeuds = N;
	nAretes = sz(X);
	nReqs = sz(S);

	for (int iArete = 0; iArete < nAretes; ++iArete){
		voisins[X[iArete]].pb(Y[iArete]);
		voisins[Y[iArete]].pb(X[iArete]);
  	}

  	vector<Req> reqs;
  	for (int iReq  = 0; iReq < nReqs; ++iReq)
  		reqs.pb({S[iReq], E[iReq], L[iReq], R[iReq], iReq});
  	


  	//Premier balayage : trouver ceux moins gros.
  	initEns();
  	for (int noeud = 0; noeud < nNoeuds; ++noeud)
  		for (int voisin : voisins[noeud]){
  			if (voisin < noeud){
  				int fus = getEns(voisin);
  				if (fus == noeud) continue;
  				enfants[0][noeud].pb(fus);
  				ens[fus] = noeud;
  			}
  		}

  	//Second balayage : trouver ceux plus gros.
  	initEns();
  	for (int noeud = nNoeuds - 1; noeud >= 0; --noeud)
  		for (int voisin : voisins[noeud]){
  			if (voisin > noeud){
  				int fus = getEns(voisin);
  				if (fus == noeud) continue;
  				enfants[1][noeud].pb(fus);
  				ens[fus] = noeud;
  			}
  		}


  	//afficher();
  	dfs(0, nNoeuds - 1, 0);
  	temps = 0;
  	dfs(1, 0, 0);

  	//Mettre les trucs biens.
  	for (Req& req : reqs){
  		//Fin arbre 0.
  		for (int iAncetre = sz(ancetres[0][req.arrivee]); iAncetre >= 0; --iAncetre){
  			if (iAncetre < sz(ancetres[0][req.arrivee]) && ancetres[0][req.arrivee][iAncetre] <= req.borneSup)
  				req.arrivee = ancetres[0][req.arrivee][iAncetre];
  		}

  		//Debut arbre 1.
  		for (int iAncetre = sz(ancetres[1][req.depart]); iAncetre >= 0; --iAncetre){
  			if (iAncetre < sz(ancetres[1][req.depart]) && ancetres[1][req.depart][iAncetre] >= req.borneInf)
  				req.depart = ancetres[1][req.depart][iAncetre];
  		}

  		aRegarder[req.arrivee].pb({req.depart, req.iReq});
  		//cout << "req " << req.depart << " " << req.arrivee << endl;
  	}

  //	afficher();

  	vector<int> res(nReqs); //TODO
  	vector<Noeud> noeuds;
  	for (int noeud = 0; noeud < nNoeuds; ++noeud)
  		noeuds.pb({noeud, fin[0][noeud]});
  	sort(all(noeuds));
  	
 // 	afficher();

  	for (Noeud noeud : noeuds){
  		//cout << noeud.id << endl;
  		update(N_NOEUDS + deb[1][noeud.id], deb[0][noeud.id]);
  		//cout << 42 << endl;

  		for (toLook req : aRegarder[noeud.id]){
  			//cout << "req " << req.root << " " << deb[1][req.root] << " " << fin[1][req.root] << endl;
  			int maxi = getMax(N_NOEUDS + deb[1][req.root], N_NOEUDS + fin[1][req.root]);
  			//cout << "lalala" << endl;
  			//cout << req.iReq << endl;
  			if (maxi >= deb[0][noeud.id])
  				res[req.iReq] = 1;
  			else
  				res[req.iReq] = 0;
  		}
  	}
  	return res;
}

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