Submission #69063

#	Time	Username	Problem	Language	Result	Execution time	Memory
69063		IvanC	Airline Route Map (JOI18_airline)	C++17	100 / 100	722 ms	31120 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;
	}

	if(N == 2){
		if(M == 0){
			InitG(2,0);
		}
		else{
			InitG(2,1);
			MakeG(0,0,1);
		}
		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 + 12;
	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
	grafo[N+11].push_back(N+12);
	grafo[N+12].push_back(N+11);

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

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

	InitG(qtd_n,qtd_m);
	int ptr = 0;
	for(int i = 1;i<=N+12;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;
	}

	if(V == 2){
		if(U == 0){
			InitMap(2,0);
		}
		else{
			InitMap(2,1);
			MakeMap(0,1);
		}
		return;
	}
	
	int N = V - 12,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+12;i++){
		if(grafo[i].size() == 1) candidatos.push_back(i);
	}

	if(candidatos.size() == 1){
		int folha = candidatos[0];
		especial = grafo[folha][0];
		for(int i : grafo[especial]){
			ehValido[i] = 1;
		}
		int menor_grau = 1024;
		for(int i = 1;i<=N+12;i++){
			if(ehValido[i]) continue;
			if(grafo[i].size() <= menor_grau){
				menor_grau = grafo[i].size();
				bit_davez = i;
			}
		}
	}
	else if(candidatos.size() == 2){
		int primeiro_cand = candidatos[0];
		int outro_cara = grafo[primeiro_cand][0];
		if(grafo[outro_cara].size() == N + 1){
			especial = outro_cara;
			bit_davez = candidatos[1];
		}
		else{
			bit_davez = primeiro_cand;
			especial = grafo[candidatos[1]][0];
		}
		for(int i : grafo[especial]){
			ehValido[i] = 1;
		}
	}

	ehValido[candidatos[0]] = 0;
	if(candidatos.size() == 2) 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+12;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+12;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);
 			}
 		}
 	}

}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(grafo[i].size() <= menor_grau){
       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
Bob.cpp:69:31: 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: 63 / 63