Submission #108146

#	Time	Username	Problem	Language	Result	Execution time	Memory
108146		hugo_pm	Werewolf (IOI18_werewolf)	C++17	15 / 100	4081 ms	67860 KiB

werewolf

#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

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vecInt;

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;

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);
}

int traiter(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]; }

	form2(i, tempsHum[subHum].fi, tempsHum[subHum].se) {
		int vl = seqHum[i];
		int tt = tempsLoup[vl].fi;
		if (tempsLoup[subLoup].fi <= tt && tt <= tempsLoup[subLoup].se) { return 1; }
	}
	return 0;
}

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);


	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(i, nbRequetes) {
		A[i] = traiter(S[i], E[i], L[i], R[i]);
	}
	return A;
}

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