Submission #404334

#	Time	Username	Problem	Language	Result	Execution time	Memory
404334		Nicholas_Patrick	Airline Route Map (JOI18_airline)	C++17	100 / 100	982 ms	25028 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <queue>
using namespace std;

void Alice( int N, int M, int A[], int B[] ){
	vector<pair<int, int>> edges;
	for(int i=M; i--;)
		edges.emplace_back(A[i], B[i]);
	for(int i=N; i--;){
		for(int j=10; j--;){
			if(i>>j&1)
				edges.emplace_back(N+j, i);
		}
		edges.emplace_back(N+10, i);
	}
	for(int i=10; i--;){
		edges.emplace_back(N+10, N+i);
		edges.emplace_back(N+11, N+i);
		if(i)
			edges.emplace_back(N+i, N+i-1);
	}
	edges.emplace_back(N+1, N+3);
	InitG(N+12, edges.size());
	while(not edges.empty()){
		MakeG(edges.size()-1, edges.back().first, edges.back().second),
		edges.pop_back();
	}
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

void Bob( int V, int U, int C[], int D[] ){
	vector<vector<int>> adjLis(V);
	for(int i=U; i--;)
		adjLis[C[i]].push_back(D[i]),
		adjLis[D[i]].push_back(C[i]);

	//finding allcon (N+10)
	int allcon=0;
	for(int i=V; i--;){
		if(adjLis[allcon].size()<adjLis[i].size())
			allcon=i;
	}

	//finding tencon (N+11)
	int tencon=0;
	adjLis[allcon].push_back(allcon);
	sort(adjLis[allcon].begin(), adjLis[allcon].end());
	for(auto i: adjLis[allcon]){
		if(i!=tencon)
			break;
		tencon++;
	}

	//finding ten (N+[0..9])
	auto ten=adjLis[tencon];
	sort(ten.begin(), ten.end());
	vector<vector<int>> adjten(10);
	for(int i=0; i<10; i++){
		for(int j: adjLis[ten[i]]){
			if(binary_search(ten.begin(), ten.end(), j))
				adjten[i].push_back(lower_bound(ten.begin(), ten.end(), j)-ten.begin());
		}
	}
	vector<int> tenord;
	//0
	for(int i=0; i<10; i++){
		if(adjten[i].size()==1 and adjten[adjten[i][0]].size()==3){
			tenord.push_back(i);
			break;
		}
	}
	//1
	tenord.push_back(adjten[tenord[0]][0]);
	//2
	for(int i=3; i--;){
		if(adjten[adjten[tenord[1]][i]].size()==2)
			tenord.push_back(adjten[tenord[1]][i]);
	}
	//3
	for(int i=3; i--;){
		if(adjten[adjten[tenord[1]][i]].size()==3)
			tenord.push_back(adjten[tenord[1]][i]);
	}
	//4
	for(int i=3; i--;){
		if(adjten[adjten[tenord[3]][i]].size()==2 and adjten[tenord[3]][i]!=tenord[2])
			tenord.push_back(adjten[tenord[3]][i]);
	}
	//5..9
	for(int i=5; i<10; i++)
		tenord.push_back(adjten[tenord[i-1]][adjten[tenord[i-1]][0]==tenord[i-2]]);
	for(int i=0; i<10; i++)
		tenord[i]=ten[tenord[i]];

	//finding all (0..N-1)
	vector<int> trueIndex(V, -1);
	int m=U-(10+V-2+10);
	for(int i=0; i<V; i++){
		if(i==allcon or i==tencon or count(tenord.begin(), tenord.end(), i))
			continue;
		sort(adjLis[i].begin(), adjLis[i].end());
		trueIndex[i]=0;
		for(int j=10; j--;){
			if(count(adjLis[i].begin(), adjLis[i].end(), tenord[j]))
				trueIndex[i]+=1<<j, m--;
		}
	}

	InitMap(V-12, m);
	for(int i=0; i<V; i++){
		if(trueIndex[i]==-1)
			continue;
		for(int j: adjLis[i]){
			if(trueIndex[j]<trueIndex[i])
				continue;
			MakeMap(trueIndex[i], trueIndex[j]);
		}
	}
}

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