Submission #316555

#	Time	Username	Problem	Language	Result	Execution time	Memory
316555		bigg	Airline Route Map (JOI18_airline)	C++14	0 / 100	744 ms	39340 KiB

Alice

#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
static vector<int> grafo[MAXN];
vector<pair<int, int> > vgrafo;
static int marc[1505][1505];
void Alice( int N, int M, int A[], int B[] ){
	for(int i = 0; i < M; i++) {
		grafo[A[i]].push_back(B[i]);
		grafo[B[i]].push_back(A[i]);
		vgrafo.push_back(make_pair(A[i], B[i]));
	}
	for(int i = 0; i < 10; i++){
		for(int j = 0; j < N; j++){
			if(j&(1<<i)){
				vgrafo.push_back(make_pair(j, N + i));
			}
		}
		vgrafo.push_back(make_pair(N + i, N + 10));
		vgrafo.push_back(make_pair(N + i, N + 11));
		if(i) vgrafo.push_back(make_pair(N+i, N + i -1));
	}
	vgrafo.push_back(make_pair(N + 1, N + 9));
	vgrafo.push_back(make_pair(N + 3, N + 9));
	for(int i = 0; i < N; i++){
		vgrafo.push_back(make_pair(N + 11, i));
	}
	InitG(N + 12, vgrafo.size());
	for(int i = 0; i < vgrafo.size(); i++){
		MakeG(i, vgrafo[i].first, vgrafo[i].second);
	}


}

Bob

#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
static vector<int> vgrafo[1505], auxbin[1505];
static vector<pair<int, int> > grafo;
static int marc1[1505][1505];
static int marc[1505], whichbin[1505], whichr[1505];
static std::vector<int> bin;

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

	int aux1, aux2, auxaux1 = 0;
	for(int i = 0; i < U; i++){
		//printf("%d %d\n",C[i], D[i] );
		vgrafo[C[i]].push_back(D[i]);
		vgrafo[D[i]].push_back(C[i]);
		if(vgrafo[D[i]].size() > auxaux1){
			aux1 = D[i];
			auxaux1 = vgrafo[D[i]].size();
		}
		if(vgrafo[C[i]].size() > auxaux1){
			aux1 = C[i];
			auxaux1 = vgrafo[C[i]].size();
		}
	}

	int n = V - 12;
	for(int i = 0; i < V; i++){
		if(i == aux1) continue;
		bool ok = 1; 
		for(auto u : vgrafo[i]){
			if(u == aux1) ok = 0;
		}
		if(ok){
			aux2 = i;
			break;
		}
	}
	//printf("%d %d\n", aux1, aux2);
	for(auto u : vgrafo[aux2]){
		marc[u] = 1;
	}
	int b0;
	for(auto u : vgrafo[aux2]){
		for(auto v : vgrafo[u]){
			if(!marc[v]) continue;
			auxbin[u].push_back(v);
		}
		if(auxbin[u].size() == 1) b0 = u;
	}
		//printf("Chegueiaqui!\n");
	int r0 = b0;
	for(int i = 0; i < 10; i++){
		bin.push_back(b0);
		whichbin[b0] = i;
		if(i == 0) b0 = auxbin[b0][0];
		else if(i == 1){
			for(auto u : auxbin[b0]){
				if(whichbin[u] == r0) continue;
				if(auxbin[u].size() > 2) continue;
				b0 = u;
				break;
			}
		}else if(i == 3){
			for(auto u : auxbin[b0]){
				if(whichbin[u] == i - 1) continue;
				if(auxbin[u].size() > 2) continue;
				b0 = u;
				break;
			}
		}else{
			for(auto u : auxbin[b0]){
				if(whichbin[u] == i - 1) continue;
				b0 = u;
				break;
			}
		}
	}	
	for(int i = 0; i < 10; i++){
		int x = bin[i];
		for(auto u : vgrafo[x]){
			if(auxbin[u].size() > 0 )continue;
			if(u == aux1) continue;
			if(u == aux2) continue;
			whichr[u] |= (1<<i);
			//printf("%d %d\n",i, whichr[u] );
		}
	}
	for(int i = 0; i < V; i++){
		if(i == aux1 || i == aux2) continue;
		if(auxbin[i].size() > 0) continue;
		for(auto u : vgrafo[i]){
			if( u == aux1 || u == aux2 ) continue;
			if(auxbin[u].size() > 0) continue;
			if(!marc1[i][u]){
				grafo.push_back(make_pair(whichr[i], whichr[u]));
			}
			marc1[i][u] = 1;
			marc1[u][i] = 1;

		}
	}



	InitMap(n, grafo.size());
	for(int i = 0; i < grafo.size(); i++){
		MakeMap(grafo[i].first, grafo[i].second);
	}

}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i = 0; i < vgrafo.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~
Alice.cpp: At global scope:
Alice.cpp:7:12: warning: 'marc' defined but not used [-Wunused-variable]
    7 | static int marc[1505][1505];
      |            ^~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:18:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |   if(vgrafo[D[i]].size() > auxaux1){
      |      ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
Bob.cpp:22:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |   if(vgrafo[C[i]].size() > auxaux1){
      |      ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
Bob.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for(int i = 0; i < grafo.size(); i++){
      |                 ~~^~~~~~~~~~~~~~
Bob.cpp:13:12: warning: 'aux2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   13 |  int aux1, aux2, auxaux1 = 0;
      |            ^~~~
Bob.cpp:94:10: warning: 'aux1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |    if( u == aux1 || u == aux2 ) continue;
      |        ~~^~~~~~~

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