Submission #924189

#	Time	Username	Problem	Language	Result	Execution time	Memory
924189		daoquanglinh2007	Airline Route Map (JOI18_airline)	C++17	100 / 100	541 ms	39720 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
 
vector <int> C, D;
 
void Alice(int N, int M, int A[], int B[]){
	for (int i = 0; i < M; i++){
		C.push_back(A[i]);
		D.push_back(B[i]);
	}
	for (int i = 0; i < N; i++){
		for (int j = 0; j < 10; j++)
			if (((i+1)>>j)&1){
				C.push_back(i);
				D.push_back(N+j);
			}
	}
	for (int i = 0; i < 10; i++){
		C.push_back(N+10);
		D.push_back(N+i);
	}
	for (int i = 0; i+1 < 10; i++){
		C.push_back(N+i);
		D.push_back(N+i+1);
	}
	for (int i = 0; i <= N; i++){
		C.push_back(N+11);
		D.push_back(i);
	}
	InitG(N+12, isz(C));
	for (int i = 0; i < isz(C); i++){
		MakeG(i, C[i], D[i]);
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
 
int N, deg[1024], b[10];
bitset <1024> adj[1024];
vector <int> G[1024], ansA, ansB;
int id[1024];

bool check(int x, int y){
	if (x == y) return 0;
	if (deg[x] != 10) return 0;
	if (deg[y] != N+1) return 0;
	if (adj[x][y]) return 0;
	if ((adj[x]&adj[y]).count() != 1) return 0;
	for (int v : G[x]){
		if (adj[y][v]) b[0] = v;
	}
	for (int i = 1; i < 10; i++){
		b[i] = -1;
		for (int v : G[x])
			if (adj[b[i-1]][v] && (i-2 < 0 || v != b[i-2])) b[i] = v;
		if (b[i] == -1) return 0;
	}
	for (int i = 1; i <= N; i++) id[i] = -1;
	for (int i = 0; i < N+12; i++){
		if (i == x || i == y || adj[x][i]) continue;
		int tmp = 0;
		for (int j = 0; j < 10; j++)
			if (adj[i][b[j]]) tmp += (1<<j);
		if (tmp < 1 || tmp > N) return 0;
		if (id[tmp] != -1) return 0;
		id[tmp] = i;
	}
	for (int i = 1; i < N; i++)
		for (int j = i+1; j <= N; j++)
			if (adj[id[i]][id[j]]){
				ansA.push_back(i-1);
				ansB.push_back(j-1);
			}
	InitMap(N, isz(ansA));
	for (int i = 0; i < isz(ansA); i++)
		MakeMap(ansA[i], ansB[i]);
	return 1;
}

void Bob(int V, int U, int C[], int D[]){
	N = V-12;
	for (int i = 0; i < U; i++){
		adj[C[i]][D[i]] = 1;
		adj[D[i]][C[i]] = 1;
		G[C[i]].push_back(D[i]);
		G[D[i]].push_back(C[i]);
		deg[C[i]]++;
		deg[D[i]]++;
	}
	for (int i = 0; i < V; i++)
		for (int j = 0; j < V; j++)
			if (check(i, j)) return;
}

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