Submission #1205371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205371		thelegendary08	Airline Route Map (JOI18_airline)	C++17	100 / 100	189 ms	23220 KiB

Alice

#include "Alicelib.h"
#include <vector>

void Alice(int N, int M, int A[], int B[]) {
	std::vector<std::pair<int, int>> edges;
	// Original graph
	for (int i = 0; i < M; i++) edges.push_back({A[i], B[i]});
	// Bit nodes to find node numbers
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < N; j++) {
			if (j & (1 << i)) edges.push_back({N + i, j});
		}
		if (i < 9) edges.push_back({N + i, N + i + 1});
	}
	// Special vertex connected to all nodes but bit nodes
	for (int i = 0; i < N; i++) edges.push_back({N + 10, i});
	// Other vertex to identify the special vertex
	edges.push_back({N + 11, N + 10});
	// Send the graph
	InitG(N + 12, edges.size());
	for (int i = 0; i < edges.size(); i++) MakeG(i, edges[i].first, edges[i].second);
}

Bob

#include "Boblib.h"
#include <vector>

std::vector<int> graph[1012];
bool adj[1012][1012], is_bit[1012], visited[1012];
int actual[1012];

void Bob(int V, int U, int C[], int D[]) {
	for (int i = 0; i < U; i++) {
		graph[C[i]].push_back(D[i]);
		graph[D[i]].push_back(C[i]);
		adj[C[i]][D[i]] = adj[D[i]][C[i]] = true;
	}
	// Find the 2 special vertices
	int special;
	for (int i = 0; i < V; i++) {
		if (graph[i].size() == 1 && graph[graph[i][0]].size() == V - 11) {
			special = graph[i][0];
			break;
		}
	}
	is_bit[special] = true;
	// Identify the bit vertices
	int last_bit = special;
	for (int i = 0; i < V; i++) {
		if (i != special && !adj[i][special]) {
			is_bit[i] = true;
			if (graph[i].size() <= graph[last_bit].size()) last_bit = i;
		}
	}
	for (int i = 9; ~i; i--) {
		visited[last_bit] = true;
		for (int j : graph[last_bit]) actual[j] += 1 << i;
		for (int j : graph[last_bit])
			if (is_bit[j] && !visited[j]) {
				last_bit = j;
				break;
			}
	}
	// Construct the graph again
	std::vector<std::pair<int, int>> edges;
	for (int i = 0; i < V; i++)
		for (int j = i + 1; j < V; j++) {
			if (adj[i][j] && !is_bit[i] && !is_bit[j])
				edges.push_back({actual[i], actual[j]});
		}
	InitMap(V - 12, edges.size());
	for (std::pair<int, int> i : edges) MakeMap(i.first, i.second);
}

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