제출 #69039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69039		IvanC	항공 노선도 (JOI18_airline)	C++17	91 / 100	724 ms	31112 KiB

Alice

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

const int MAXN = 1020;

static vector<int> grafo[MAXN];

void Alice( int N, int M, int A[], int B[] ){
	
	if(N == 1){
		InitG(1,0);
		return;
	}

	// Padrao
	for(int i = 0;i<M;i++){
		int x = A[i];
		int y = B[i];
		x++;y++; // 1-indexado, se nao falha
		grafo[x].push_back(y);
		grafo[y].push_back(x);
	}

	int qtd_n = N + 13;
	int qtd_m = 0;

	// Bits
	for(int i = 0;i<10;i++){
		int pot = (1 << i);
		int idx = N + i + 1;
		for(int j = 1;j<=N;j++){
			if(pot & j){
				grafo[j].push_back(idx);
				grafo[idx].push_back(j);
			}
		}
	}

	// Ligacao bits
	for(int i = 0;i+1<10;i++){
		int idx1 = N + i + 1;
		int idx2 = N + i + 2;
		grafo[idx1].push_back(idx2);
		grafo[idx2].push_back(idx1);
	}

	// folha-1
	grafo[N+10].push_back(N+11);
	grafo[N+11].push_back(N+10);

	//folha-2
	grafo[N+12].push_back(N+13);
	grafo[N+13].push_back(N+12);

	// grau alto
	for(int i = 1;i<=N;i++){
		grafo[i].push_back(N+13);
		grafo[N+13].push_back(i);
	}

	for(int i = 1;i<=N+13;i++) qtd_m += grafo[i].size();
	qtd_m /=2;

	InitG(qtd_n,qtd_m);
	int ptr = 0;
	for(int i = 1;i<=N+13;i++){
		for(int j : grafo[i]){
			if(i >= j) continue;
			//printf("Ptr %d Alice I %d J %d\n",ptr,i,j);
			MakeG(ptr,i-1,j-1);
			ptr++;
		}
	}

}

Bob

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

const int MAXN = 1020;

static vector<int> grafo[MAXN];
static int ehValido[MAXN],somatorio[MAXN];

void Bob( int V, int U, int C[], int D[] ){

	//printf("##############################\n");
	memset(ehValido,0,sizeof(ehValido));
	memset(somatorio,0,sizeof(somatorio));

	// caso especial
	if(V == 1){
		InitMap(1,0);
		return;
	}
	
	int N = V - 13,M = 0,especial = 0,bit_davez = 0;

	// recuperando o grafo
	for(int i = 0;i<U;i++){
		int x = C[i];
		int y = D[i];
		x++;y++;
		grafo[x].push_back(y);
		grafo[y].push_back(x);
		//printf("G %d %d\n",x,y);
	}

	vector<int> candidatos;

	for(int i = 1;i<=N+13;i++){
		if(grafo[i].size() == 1) candidatos.push_back(i);
	}

	// Descobrindo o primeiro bit
	int primeiro_cand = candidatos[0];
	int outro_cara = grafo[primeiro_cand][0];
	//printf("C1 %d C2 %d O %d\n",candidatos[0],candidatos[1],outro_cara);
	if(grafo[outro_cara].size() == N + 1){
	//	printf("Caso 1\n");
		bit_davez = grafo[candidatos[1]][0];
		especial = outro_cara;
	}
	else{
	//	printf("Caso 2\n");
		bit_davez = outro_cara;
		especial = grafo[candidatos[1]][0];
	}

	for(int i : grafo[especial]){
		ehValido[i] = 1;
	}

	ehValido[candidatos[0]] = 0;
	ehValido[candidatos[1]] = 0;
 
 	for(int vez = 9;vez>=0;vez--){
 		
 		int nxt = 0,pot = (1 << vez);
 		//printf("Meu %d\n",bit_davez);

 		for(int i : grafo[bit_davez]){
 			if(grafo[i].size() <= 1){
 				continue;
 			}
 			if(!ehValido[i]){
 				nxt = i;
 			}
 			else{
 				//printf("Add %d AH %d\n",pot,i);
 				somatorio[i] += pot;
 			}
 		}

 		grafo[bit_davez].clear();

 		bit_davez = nxt;

 	}

 	for(int i = 1;i<=N+13;i++){
 		for(int j : grafo[i]){
 			if(!ehValido[i] || !ehValido[j]) continue;
 			if(i <= j){
 				M++;
 			}
 		}
 	}

 	InitMap(N,M);

 	for(int i = 1;i<=N+13;i++){
 		for(int j : grafo[i]){
 			if(!ehValido[i] || !ehValido[j]) continue;
 			if(i <= j){
 				//printf("Bob I %d J %d (%d %d)\n",i,j,somatorio[i]-1,somatorio[j]-1);
 				MakeMap(somatorio[i] - 1,somatorio[j] - 1);
 			}
 		}
 	}

}

컴파일 시 표준 에러 (stderr) 메시지

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:44:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(grafo[outro_cara].size() == N + 1){
     ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 15 / 15
• Subtask 3: 54 / 63