oj.uz

Submission #394908

# Submission time Handle Problem Language Result Execution time Memory
394908 2021-04-27T13:22:15 Z Mounir Werewolf (IOI18_werewolf) C++14
100 / 100
 1205 ms 181520 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 74204 KB Output is correct
2 Correct 49 ms 74280 KB Output is correct
3 Correct 47 ms 74168 KB Output is correct
4 Correct 47 ms 74360 KB Output is correct
5 Correct 49 ms 74256 KB Output is correct
6 Correct 47 ms 74180 KB Output is correct
7 Correct 48 ms 74188 KB Output is correct
8 Correct 46 ms 74208 KB Output is correct
9 Correct 49 ms 74180 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 74204 KB Output is correct
2 Correct 49 ms 74280 KB Output is correct
3 Correct 47 ms 74168 KB Output is correct
4 Correct 47 ms 74360 KB Output is correct
5 Correct 49 ms 74256 KB Output is correct
6 Correct 47 ms 74180 KB Output is correct
7 Correct 48 ms 74188 KB Output is correct
8 Correct 46 ms 74208 KB Output is correct
9 Correct 49 ms 74180 KB Output is correct
10 Correct 55 ms 75464 KB Output is correct
11 Correct 55 ms 75484 KB Output is correct
12 Correct 55 ms 75204 KB Output is correct
13 Correct 55 ms 75692 KB Output is correct
14 Correct 56 ms 75612 KB Output is correct
15 Correct 56 ms 75600 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 141904 KB Output is correct
2 Correct 1105 ms 161552 KB Output is correct
3 Correct 911 ms 154952 KB Output is correct
4 Correct 795 ms 147372 KB Output is correct
5 Correct 771 ms 147116 KB Output is correct
6 Correct 784 ms 145728 KB Output is correct
7 Correct 807 ms 140420 KB Output is correct
8 Correct 974 ms 161372 KB Output is correct
9 Correct 780 ms 154936 KB Output is correct
10 Correct 621 ms 146780 KB Output is correct
11 Correct 618 ms 146920 KB Output is correct
12 Correct 710 ms 145212 KB Output is correct
13 Correct 1201 ms 174304 KB Output is correct
14 Correct 1182 ms 174168 KB Output is correct
15 Correct 1146 ms 174240 KB Output is correct
16 Correct 1182 ms 174152 KB Output is correct
17 Correct 780 ms 140420 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 74204 KB Output is correct
2 Correct 49 ms 74280 KB Output is correct
3 Correct 47 ms 74168 KB Output is correct
4 Correct 47 ms 74360 KB Output is correct
5 Correct 49 ms 74256 KB Output is correct
6 Correct 47 ms 74180 KB Output is correct
7 Correct 48 ms 74188 KB Output is correct
8 Correct 46 ms 74208 KB Output is correct
9 Correct 49 ms 74180 KB Output is correct
10 Correct 55 ms 75464 KB Output is correct
11 Correct 55 ms 75484 KB Output is correct
12 Correct 55 ms 75204 KB Output is correct
13 Correct 55 ms 75692 KB Output is correct
14 Correct 56 ms 75612 KB Output is correct
15 Correct 56 ms 75600 KB Output is correct
16 Correct 811 ms 141904 KB Output is correct
17 Correct 1105 ms 161552 KB Output is correct
18 Correct 911 ms 154952 KB Output is correct
19 Correct 795 ms 147372 KB Output is correct
20 Correct 771 ms 147116 KB Output is correct
21 Correct 784 ms 145728 KB Output is correct
22 Correct 807 ms 140420 KB Output is correct
23 Correct 974 ms 161372 KB Output is correct
24 Correct 780 ms 154936 KB Output is correct
25 Correct 621 ms 146780 KB Output is correct
26 Correct 618 ms 146920 KB Output is correct
27 Correct 710 ms 145212 KB Output is correct
28 Correct 1201 ms 174304 KB Output is correct
29 Correct 1182 ms 174168 KB Output is correct
30 Correct 1146 ms 174240 KB Output is correct
31 Correct 1182 ms 174152 KB Output is correct
32 Correct 780 ms 140420 KB Output is correct
33 Correct 1000 ms 155820 KB Output is correct
34 Correct 417 ms 104796 KB Output is correct
35 Correct 1146 ms 159676 KB Output is correct
36 Correct 963 ms 155792 KB Output is correct
37 Correct 1074 ms 158696 KB Output is correct
38 Correct 985 ms 156460 KB Output is correct
39 Correct 1027 ms 179988 KB Output is correct
40 Correct 1127 ms 162756 KB Output is correct
41 Correct 904 ms 156548 KB Output is correct
42 Correct 821 ms 154088 KB Output is correct
43 Correct 1205 ms 177704 KB Output is correct
44 Correct 1035 ms 157580 KB Output is correct
45 Correct 937 ms 181520 KB Output is correct
46 Correct 1004 ms 180660 KB Output is correct
47 Correct 1134 ms 173992 KB Output is correct
48 Correct 1189 ms 173880 KB Output is correct
49 Correct 1145 ms 173944 KB Output is correct
50 Correct 1132 ms 173848 KB Output is correct
51 Correct 1066 ms 162348 KB Output is correct
52 Correct 1044 ms 162004 KB Output is correct