oj.uz

Submission #188517

# Submission time Handle Problem Language Result Execution time Memory
188517 2020-01-13T08:26:19 Z dolphingarlic Airline Route Map (JOI18_airline) C++14
0 / 100
 775 ms 30464 KB 
#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 (i & (1 << j)) 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);
}

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

std::vector<int> graph[1012];
bool adj[1012][1012], is_bit[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) {
			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--) {
		for (int j : graph[last_bit]) actual[j] += 1 << i;
		for (int j : graph[last_bit]) if (is_bit[j]) {
			last_bit = j;
			break;
		}
	}
	// Construct the graph again
	std::vector<std::pair<int, int>> edges;
	for (int i = 0; i < V; i++) {
		if (is_bit[i]) continue;
		for (int j : graph[i]) if (!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

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:22:18: warning: 'special' may be used uninitialized in this function [-Wmaybe-uninitialized]
  is_bit[special] = true;
  ~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6896 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6896 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 775 ms 30464 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -