Submission #95400

#	Time	Username	Problem	Language	Result	Execution time	Memory
95400		Retro3014	Airline Route Map (JOI18_airline)	C++17	100 / 100	737 ms	31208 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

vector<pair<int, int> > Edge;

void Alice(int N, int M, int A[], int B[] ){
	for(int i=0; i<M; i++){
		Edge.push_back(make_pair(A[i], B[i]));
	}
	int two = 1;
	for(int i=0; i<10; i++){
		for(int j=0; j<N; j++){
			if((j&two)!=0){
				Edge.push_back(make_pair(j, i+N));
			}
		}
		two*=2;
	}
	for(int i=0; i<N; i++){
		Edge.push_back(make_pair(N+10, i));
		Edge.push_back(make_pair(N+11, i));
	}
	for(int i=0; i<9; i++){
		Edge.push_back(make_pair(N+i, N+10));
		Edge.push_back(make_pair(N+i, N+i+1));
	}
	InitG(N+12, Edge.size());
	for(int i=0; i<Edge.size(); i++){
		MakeG(i, Edge[i].first, Edge[i].second);
	}
	return;
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

#define MAX_V 1012

vector<int> gp[MAX_V+1];
bool chk[MAX_V+1];
int index[MAX_V+1];
bool vst[MAX_V+1];
bool f[MAX_V+1];

vector<pair<int, int> > edge;

void Bob( int V, int U, int C[], int D[] ){
	for(int i=0; i<U; i++){
		gp[C[i]].push_back(D[i]);
		gp[D[i]].push_back(C[i]);
	}
	vector<int> idx2(0);
	for(int i=0; i<V; i++){
		if(gp[i].size()==V-3)	idx2.push_back(i);
	}
	int idx;
	int a = 0, b = 0;
	while(1){
		idx = idx2.back();	idx2.pop_back();
		for(int i=0; i<V; i++){
			vst[i] = false;
		}
		for(int i=0; i<gp[idx].size(); i++){
			vst[gp[idx][i]] = true;
		}
		a = b = 0;
		for(int i=0; i<V; i++){
			if(i==idx)	continue;
			if(vst[i]==false){
				if(a==0)	a = i;
				else	b = i;
			}
		}
		if(gp[a].size()>gp[b].size()){int tmp = a; a = b; b = tmp;}
		if(gp[b].size()==V-12)	break;
	}
	for(int i=0; i<V; i++){
		chk[i] = true;
	}
	chk[idx] = false; chk[b] = false;
	for(int i=0; i<gp[b].size(); i++){
		chk[gp[b][i]] = false;
	}
	int two = (1<<9);
	for(int T=0; T<10; T++){
		int nxt = 0;
		for(int i=0; i<gp[a].size(); i++){
			if(chk[gp[a][i]]){
				if(!f[gp[a][i]]){
					nxt = gp[a][i];
				}
				continue;
			}
			index[gp[a][i]]+=two;
		}
		f[a] = true;
		a = nxt;
		two/=2;
	}
	chk[idx] = true; chk[b] = true;
	for(int i=0; i<U; i++){
		if(chk[D[i]] || chk[C[i]])	continue;
		edge.push_back(make_pair(index[D[i]], index[C[i]]));
	}
	InitMap(V-12, edge.size());
	for(int i=0; i<edge.size(); i++){
		MakeMap(edge[i].first, edge[i].second);
	}
	return;
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:35:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<Edge.size(); i++){
               ~^~~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:28:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(gp[i].size()==V-3) idx2.push_back(i);
      ~~~~~~~~~~~~^~~~~
Bob.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<gp[idx].size(); i++){
                ~^~~~~~~~~~~~~~~
Bob.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(gp[b].size()==V-12) break;
      ~~~~~~~~~~~~^~~~~~
Bob.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[b].size(); i++){
               ~^~~~~~~~~~~~~
Bob.cpp:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<gp[a].size(); i++){
                ~^~~~~~~~~~~~~
Bob.cpp:80:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge.size(); i++){
               ~^~~~~~~~~~~~

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