oj.uz

Submission #69452

# Submission time Handle Problem Language Result Execution time Memory
69452 2018-08-21T00:02:35 Z IvanC Amusement Park (JOI17_amusement_park) C++17
0 / 100
 96 ms 34744 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10011;
const int MAXL = 60;

static vector<int> grafo[MAXN],tree[MAXN],lista;
static bitset<MAXN> adjMat[MAXN];
static int digito[MAXL],pai[MAXN],contador[MAXN],idx[MAXN],relevante[MAXN];

static void bfs(){

	memset(contador,0,sizeof(contador));
	pai[0] = -1;
	contador[0] = 1;
	queue<int> fila;
	fila.push(0);

	while(!fila.empty()){
		int v = fila.front();
		fila.pop();
		lista.push_back(v);
		for(int u : grafo[v]){
			if(contador[u]) continue;
			contador[u] = 1;
			pai[u] = v;
			fila.push(u);
			adjMat[v][u] = 1;
			adjMat[u][v] = 1;
		}
	}

	memset(contador,0,sizeof(contador));

}

static void build_first(){

	vector<int> primeiro;
	for(int i = 0;i<MAXL;i++){
		primeiro.push_back(lista[i]);
		idx[primeiro.back()] = i;
	}

	for(int i : primeiro) tree[i] = primeiro;

}

static void extend_tree(int v){

	vector<int> copia = tree[pai[v]];

	for(int u : copia) relevante[u] = 1;

	for(int u : copia){
		int w = pai[u];
		if(w == -1 || !relevante[w]) continue;
		contador[u]++;
		contador[w]++;
	}

	int achei = -1;

	for(int u : copia){
		if(u == pai[v]) continue;
		if(contador[u] == 1){
			achei = u;
			break;
		}
	}

	for(int u : copia){
		contador[u] = 0;
		relevante[u] = 0;
		if(u != achei) tree[v].push_back(u);
	}

	tree[v].push_back(v);
	idx[v] = idx[achei];

}

void Joi(int N, int M, int A[], int B[], long long X, int T){
	
	for(int i = 0;i<MAXL;i++){
		if(X & (1 << i)) digito[i] = 1;
		else digito[i] = 0;
	}

	for(int i = 0;i<M;i++){
		grafo[A[i]].push_back(B[i]);
		grafo[B[i]].push_back(A[i]);
	}

	bfs();
	build_first();
	for(int i = MAXL;i<N;i++) extend_tree(lista[i]);

	for(int i = 0;i<N;i++) MessageBoard(i, digito[idx[i]] );

}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10011;
const int MAXL = 60;

static vector<int> grafo[MAXN],tree[MAXN],lista;
static bitset<MAXN> adjMat[MAXN];
static int digito[MAXL],pai[MAXN],contador[MAXN],idx[MAXN],qual_digito[MAXN],relevante[MAXN];

static void bfs(){

	memset(contador,0,sizeof(contador));
	pai[0] = -1;
	contador[0] = 1;
	queue<int> fila;
	fila.push(0);

	while(!fila.empty()){
		int v = fila.front();
		fila.pop();
		lista.push_back(v);
		for(int u : grafo[v]){
			if(contador[u]) continue;
			contador[u] = 1;
			pai[u] = v;
			fila.push(u);
			adjMat[v][u] = 1;
			adjMat[u][v] = 1;
		}
	}

	memset(contador,0,sizeof(contador));

}

static void build_first(){

	vector<int> primeiro;
	for(int i = 0;i<MAXL;i++){
		primeiro.push_back(lista[i]);
		idx[primeiro.back()] = i;
	}

	for(int i : primeiro) tree[i] = primeiro;

}

static void extend_tree(int v){

	vector<int> copia = tree[pai[v]];

	for(int u : copia) relevante[u] = 1;

	for(int u : copia){
		int w = pai[u];
		if(w == -1 || !relevante[w]) continue;
		contador[u]++;
		contador[w]++;
	}

	int achei = -1;

	for(int u : copia){
		if(u == pai[v]) continue;
		if(contador[u] == 1){
			achei = u;
			break;
		}
	}

	for(int u : copia){
		contador[u] = 0;
		relevante[u] = 0;
		if(u != achei) tree[v].push_back(u);
	}

	tree[v].push_back(v);
	idx[v] = idx[achei];

}

static void dfs(int v){

	contador[v] = 1;
	digito[idx[v]] = qual_digito[v];

	for(int u : grafo[v]){
		if(!adjMat[u][v] || contador[u] || !relevante[u]) continue;
		qual_digito[u] = Move(u);
		dfs(u);
		Move(v);
	}

}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {

	for(int i = 0;i<M;i++){
		grafo[A[i]].push_back(B[i]);
		grafo[B[i]].push_back(A[i]);
	}

	bfs();
	build_first();
	for(int i = MAXL;i<N;i++) extend_tree(lista[i]);

	memset(relevante,0,sizeof(relevante));
	for(int i : tree[P]) relevante[i] = 1;
	qual_digito[P] = V;
	dfs(P);

	long long ans = 0;
	for(int i = 0;i<MAXL;i++) if(digito[i]) ans += (1LL << i);

	return ans;

}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1888 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 34636 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 34656 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 34664 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 34744 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -