Submission #605190

#	Time	Username	Problem	Language	Result	Execution time	Memory
605190		alireza_kaviani	Airline Route Map (JOI18_airline)	C++17	100 / 100	762 ms	29364 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define X		first
#define Y 		second
#define SZ(x)	int((x).size())

const int MAXN = 1510;
const int LOG = 10;

void Alice(int N, int M, int A[], int B[]){
	vector<pii> E;
	for(int i = 0 ; i < M ; i++){
		E.push_back({A[i] , B[i]});
	}
	for(int i = 0 ; i < N ; i++){
		E.push_back({i , N});
	}
	for(int i = N + 1 ; i < N + LOG ; i++){
		E.push_back({i , i + 1});
	}
	E.push_back({N , N + LOG + 1});
	for(int i = 0 ; i < LOG ; i++){
		for(int j = 0 ; j < N ; j++){
			if((j + 1) & (1 << i)){
				E.push_back({j , N + LOG - i});
			}
		}
	}
	InitG(N + LOG + 2 , SZ(E));
	for(int i = 0 ; i < SZ(E) ; i++){
		MakeG(i , E[i].X , E[i].Y);
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define X		first
#define Y 		second
#define SZ(x)	int((x).size())

const int MAXN = 1510;
const int LOG = 10;

int type[MAXN] , val[MAXN] , ind[MAXN];
vector<int> adj[MAXN] , vec;

void DFS(int v){
	type[v] = 2;
	vec.push_back(v);
	for(int u : adj[v]){
		if(type[u])	continue;
		DFS(u);
	}
}

void Bob(int N, int M, int A[], int B[]){
	int n = N - LOG - 2;
	if(n == 1){
		InitMap(1 , 0);
		return;
	}
	for(int i = 0 ; i < M ; i++){
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	int v = -1;
	for(int i = 0 ; i < N ; i++){
		if(SZ(adj[i]) == 1){
			if(SZ(adj[adj[i][0]]) >= n + 1){
				v = i;
			}
		}
	}
	v = adj[v][0]; type[v] = 3;
	for(int i = 0 ; i < M ; i++){
		if(A[i] == v)	type[B[i]] = 1;
		if(B[i] == v)	type[A[i]] = 1;
	}
	int u = -1;
	for(int i = 0 ; i < N ; i++){
		if(type[i] == 0){
			int cnt = 0;
			for(int j : adj[i]){
				cnt += (type[j] == 0);
			}
			if(cnt == 1){
				u = i;
				break;
			}
		}
	}
	DFS(u);
	if(SZ(adj[vec[0]]) < SZ(adj[vec.back()])){
		reverse(vec.begin() , vec.end());
	}
	assert(SZ(vec) == LOG);
	for(int i = 0 ; i < LOG ; i++){
		val[vec[i]] = i;
		type[vec[i]] = 2;
	}
	vector<pii> E;
	for(int i = 0 ; i < M ; i++){
		if(type[A[i]] > type[B[i]])	swap(A[i] , B[i]);
		if(type[A[i]] == 1 && type[B[i]] == 2){
			ind[A[i]] |= (1 << val[B[i]]);
		}
		if(type[A[i]] == 1 && type[B[i]] == 1){
			E.push_back({A[i] , B[i]});
		}
	}
	InitMap(n , SZ(E));
	for(pii i : E){
		MakeMap(ind[i.X] - 1 , ind[i.Y] - 1);
	}
}

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