Submission #188536

#	Time	Username	Problem	Language	Result	Execution time	Memory
188536		dolphingarlic	Airline Route Map (JOI18_airline)	C++14	100 / 100	935 ms	30968 KiB

Alice

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

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 <vector>
#include "Boblib.h"

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);
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:21:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < edges.size(); i++)
                     ~~^~~~~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:17:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (graph[i].size() == 1 && graph[graph[i][0]].size() == V - 11) {
                               ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
Bob.cpp:22:18: warning: 'special' may be used uninitialized in this function [-Wmaybe-uninitialized]
  is_bit[special] = true;
  ~~~~~~~~~~~~~~~~^~~~~~

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