Submission #56669

#	Time	Username	Problem	Language	Result	Execution time	Memory
56669		khsoo01	Airline Route Map (JOI18_airline)	C++11	100 / 100	722 ms	31088 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;

int re[1024];

vector<pii> edg;

void Alice (int N, int M, int A[], int B[]) {
	for(int i=0;i<M;i++) {
		edg.push_back({A[i], B[i]});
	}
	for(int i=0,j=0;i<1000;i++,j++) {
		while(__builtin_popcount(j) >= 9) j++;
		re[i] = j;
	}
	for(int i=0;i<10;i++) {
		if(i) edg.push_back({N+i-1, N+i});
		for(int j=0;j<N;j++) {
			if((1<<i) & re[j]) edg.push_back({N+i, j});
		}
	}
	for(int i=0;i<N;i++) {
		edg.push_back({N+10, i});
	}
	for(int i=0;i<N+10;i++) {
		edg.push_back({N+11, i});
	}
	InitG(N+12, edg.size());
	for(int i=0;i<(int)edg.size();i++) {
		int A, B;
		tie(A, B) = edg[i];
		MakeG(i, A, B);
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;

int idx[1024], rev[1024];
bool chk[1024];

vector<int> adj[1024], oth[1024], ep, line;
vector<pii> ans;

void Bob( int V, int U, int C[], int D[] ){
	for(int i=0;i<U;i++) {
		adj[C[i]].push_back(D[i]);
		adj[D[i]].push_back(C[i]);
	}
	int VA = 0, VB = V*(V-1)/2;
	for(int i=0;i<V;i++) {
		if(adj[i].size() > adj[VA].size()) VA = i;
	}
	chk[VA] = true;
	VB -= VA;
	for(auto &T : adj[VA]) {
		VB -= T;
	}
	chk[VB] = true;
	for(auto &T : adj[VB]) {
		chk[T] = true;
	}
	for(int i=0;i<V;i++) {
		if(chk[i]) continue;
		for(auto &T : adj[i]) {
			if(!chk[T]) oth[i].push_back(T);
		}
		if(oth[i].size() == 1) ep.push_back(i);
	}
	if(adj[ep[0]].size() < adj[ep[1]].size()) {
		swap(ep[0], ep[1]);
	}
	for(int i=ep[0],j=-1;;) {
		line.push_back(i);
		if(~j && oth[i].size() == 1) break;
		for(auto &T : oth[i]) {
			if(T != j) {
				j = i;
				i = T;
				break;
			}
		}
	}
	chk[VA] = false;
	chk[VB] = false;
	for(int i=0;i<10;i++) {
		for(auto &T : adj[line[i]]) {
			if(chk[T]) idx[T] += (1<<i);
		}
	}
	for(int i=0,j=0;i<1000;i++,j++) {
		while(__builtin_popcount(j) >= 9) j++;
		rev[j] = i;
	}
	for(int i=0;i<U;i++) {
		if(!chk[C[i]] || !chk[D[i]]) continue;
		ans.push_back({rev[idx[C[i]]], rev[idx[D[i]]]});
	}
	InitMap(V-12, ans.size());
	for(auto &T : ans) {
		MakeMap(T.X, T.Y);
	}
}

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