oj.uz

Submission #108146

# Submission time Handle Problem Language Result Execution time Memory
108146 2019-04-27T17:02:22 Z hugo_pm Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 67860 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5888 KB Output is correct
2 Correct 9 ms 5888 KB Output is correct
3 Correct 8 ms 5888 KB Output is correct
4 Correct 9 ms 5760 KB Output is correct
5 Correct 8 ms 5888 KB Output is correct
6 Correct 8 ms 5888 KB Output is correct
7 Correct 9 ms 5888 KB Output is correct
8 Correct 7 ms 5888 KB Output is correct
9 Correct 7 ms 5888 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5888 KB Output is correct
2 Correct 9 ms 5888 KB Output is correct
3 Correct 8 ms 5888 KB Output is correct
4 Correct 9 ms 5760 KB Output is correct
5 Correct 8 ms 5888 KB Output is correct
6 Correct 8 ms 5888 KB Output is correct
7 Correct 9 ms 5888 KB Output is correct
8 Correct 7 ms 5888 KB Output is correct
9 Correct 7 ms 5888 KB Output is correct
10 Correct 18 ms 6784 KB Output is correct
11 Correct 17 ms 6784 KB Output is correct
12 Correct 14 ms 6784 KB Output is correct
13 Correct 19 ms 6912 KB Output is correct
14 Correct 17 ms 6912 KB Output is correct
15 Correct 22 ms 6784 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 928 ms 62168 KB Output is correct
2 Execution timed out 4081 ms 67860 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5888 KB Output is correct
2 Correct 9 ms 5888 KB Output is correct
3 Correct 8 ms 5888 KB Output is correct
4 Correct 9 ms 5760 KB Output is correct
5 Correct 8 ms 5888 KB Output is correct
6 Correct 8 ms 5888 KB Output is correct
7 Correct 9 ms 5888 KB Output is correct
8 Correct 7 ms 5888 KB Output is correct
9 Correct 7 ms 5888 KB Output is correct
10 Correct 18 ms 6784 KB Output is correct
11 Correct 17 ms 6784 KB Output is correct
12 Correct 14 ms 6784 KB Output is correct
13 Correct 19 ms 6912 KB Output is correct
14 Correct 17 ms 6912 KB Output is correct
15 Correct 22 ms 6784 KB Output is correct
16 Correct 928 ms 62168 KB Output is correct
17 Execution timed out 4081 ms 67860 KB Time limit exceeded
18 Halted 0 ms 0 KB -