Submission #44595

#	Time	Username	Problem	Language	Result	Execution time	Memory
44595		aome	Airline Route Map (JOI18_airline)	C++17	100 / 100	794 ms	30816 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1020;

int C[N * N], D[N * N];

void Alice(int N, int M, int A[], int B[]) {
	int V = N + 12, U = 0;
	for (int i = 0; i < M; ++i) {
		C[U] = A[i], D[U] = B[i], U++;
	}
	for (int i = 0; i < N + 10; ++i) {
		C[U] = i, D[U] = N + 10, U++;
	}
	for (int i = 0; i < 10; ++i) {
		C[U] = N + i, D[U] = N + 11, U++;
	}
	for (int i = 1; i < 10; ++i) {
		C[U] = N + i - 1, D[U] = N + i, U++;
	}
	for (int i = 1; i < 8; ++i) {
		C[U] = N + i, D[U] = N + 9, U++;
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 10; ++j) {
			if (i >> j & 1) {
				C[U] = i, D[U] = N + j, U++;
			}
		}
	}
	InitG(V, U);
	for (int i = 0; i < U; ++i) {
		MakeG(i, C[i], D[i]);
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1020;

int A[N * N], B[N * N], deg[N];
int val_bit[N];
bool E[N][N], is_bit[N];
vector<int> vec;

void Bob(int V, int U, int C[], int D[]) {
	int N, M;
	N = V - 12, M = 0;
	for (int i = 0; i < U; ++i) {
		deg[C[i]]++, deg[D[i]]++;
		E[C[i]][D[i]] = E[D[i]][C[i]] = 1;
	}
	int _11th = -1, _12th = -1;
	for (int i = 0; i < V; ++i) {
		if (deg[i] == V - 2) _11th = i; 
	}
	assert(_11th != -1);
	for (int i = 0; i < V; ++i) {
		if (i != _11th && !E[i][_11th]) _12th = i;
	}
	assert(_12th != -1);
	for (int i = 0; i < V; ++i) {
		if (E[_12th][i]) {
			is_bit[i] = 1, vec.push_back(i);
		}
	}
	for (auto i : vec) {
		deg[i] = 0, val_bit[i] = -1;
		for (auto j : vec) deg[i] += E[i][j];
	}	
	int _1st = -1, _10th = -1;
	for (auto i : vec) {
		if (deg[i] == 1) _1st = i;
		if (deg[i] == 8) _10th = i;
	}
	assert(_1st != -1);
	assert(_10th != -1);
	val_bit[_1st] = 0, val_bit[_10th] = 9;
	int cur = _1st, val = 1;
	while (1) {
		bool found = 0;
		for (auto i : vec) {
			if (E[cur][i] && val_bit[i] == -1) {
				found = 1, cur = i; break;
			} 
		}
		if (!found) break;
		val_bit[cur] = val++;
	}
	for (int i = 0; i < U; ++i) {
		if (C[i] == _11th || C[i] == _12th || is_bit[C[i]]) continue;
		if (D[i] == _11th || D[i] == _12th || is_bit[D[i]]) continue;
		for (auto j : vec) {
			if (E[C[i]][j]) A[M] += 1 << val_bit[j];
			if (E[D[i]][j]) B[M] += 1 << val_bit[j];
		}
		M++;
	}
	InitMap(N, M);
	for (int i = 0; i < M; ++i) {
		MakeMap(A[i], B[i]);
	}
}

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