Submission #846568

#	Time	Username	Problem	Language	Result	Execution time	Memory
846568		PanosPask	Airline Route Map (JOI18_airline)	C++14	100 / 100	607 ms	31944 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#define pb push_back
#define CHECK_BIT(val, pos) (val & (1 << pos))
#include <vector>

const int BITS = 10;

using namespace std;

int V, E;

vector<int> C;
vector<int> D;

void Alice( int N, int M, int A[], int B[] ){
	// Just create some new nodes

	V = N;
	E = M;

	// First the bitnodes
	for (int b = 0; b < BITS; b++) {
		for (int i = 0; i < N; i++)
			if (CHECK_BIT(i, b)) {
				C.pb(i);
				D.pb(V);
			}
		if (b) {
			C.pb(V);
			D.pb(V - 1);
		}
		V++;
	}

	// Then the one with all the connections
	for (int i = 1; i <= BITS; i++) {
		C.pb(V);
		D.pb(V - i);
	}
	V++;

	// Then the one with all but this
	for (int i = 0; i < V - 1; i++) {
		C.pb(V);
		D.pb(i);
	}
	V++;

	InitG(V, C.size() + M);
	for (int i = 0; i < M; i++)
		MakeG(i, A[i], B[i]);
	for (int i = 0; i < C.size(); i++)
		MakeG(i + M, C[i], D[i]);

	return;;
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
#define pb push_back

const int BITS = 10;

using namespace std;

// Bit nodes, in little endian order
vector<int> bitnodes;
vector<int> real_order;
vector<vector<int>> adj_list;

vector<int> actual;

int edge_ttl = 0;

vector<bool> banned;

int inside(int a, vector<int>& v)
{
	int p = lower_bound(v.begin(), v.end(), a) - v.begin();
	if (p != v.size() && v[p] == a)
		return true;

	return false;
}

int decode(int node)
{
	int res = 0;
	for (int i = 0; i < BITS; i++) {
		if (inside(bitnodes[i], adj_list[node])) {
			res += (1 << i);
			edge_ttl--;
		}
	}

	return res;
}

void find_next_bitnode(int node, int par)
{
	for (auto i : bitnodes) {
		if (i == node || i == par)
			continue;

		if (inside(i, adj_list[node])) {
			real_order.pb(i);
			find_next_bitnode(i, node);
			return;
		}
	}
}

void Bob( int V, int U, int C[], int D[] )
{
	bitnodes.clear();
	adj_list.clear();
	actual.clear();

	edge_ttl = U;

	adj_list.resize(V);
	banned.assign(V, false);
	actual.assign(V, -1);

	for (int i = 0; i < U; i++) {
		adj_list[C[i]].pb(D[i]);
		adj_list[D[i]].pb(C[i]);
	}

	int outl = -1;
	for (int i = 0; i < V; i++) {
		if (adj_list[i].size() == V - 2)
			outl = i;

		sort(adj_list[i].begin(), adj_list[i].end());
	}

	// Find the node not connected to outlier
	int curp = 0;
	int special = -1;
	for (int i = 0; i < V - 1; i++) {
		if (i == outl)
			continue;

		if (adj_list[outl][curp++] != i) {
			special = i;
			break;
		}
	}
	if (special == -1)
		special = V - 1;

	banned[special] = banned[outl] = true;
	edge_ttl -= adj_list[special].size() + adj_list[outl].size();
	edge_ttl -= BITS - 1;

	// Found special, find bitnodes
	for (auto neigh : adj_list[special]) {
		bitnodes.pb(neigh);
		banned[neigh] = true;
	}

	// Find correct ordering
	// Find one of the starts

	int st = -1;
	for (int i = 0; i < BITS; i++) {
		int cnt = 0;
		for (int j = 0; j < BITS; j++) {
			if (inside(bitnodes[j], adj_list[bitnodes[i]]))
				cnt++;
		}
		if (cnt == 1)
			st = bitnodes[i];
	}
	real_order.pb(st);
	find_next_bitnode(st, -1);

	if (adj_list[real_order.front()].size() < adj_list[real_order.back()].size())
		reverse(real_order.begin(), real_order.end());
	bitnodes = real_order;

	for (int i = 0; i < V; i++) {
		if (!banned[i])
			actual[i] = decode(i);
	}

	InitMap(V - BITS - 2, edge_ttl);

	for (int i = 0; i < V; i++)
		for (auto j : adj_list[i]) {
			if (!banned[i] && !banned[j] && actual[i] < actual[j])
				MakeMap(actual[i], actual[j]);
		}
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for (int i = 0; i < C.size(); i++)
      |                  ~~^~~~~~~~~~

Bob.cpp: In function 'int inside(int, std::vector<int>&)':
Bob.cpp:26:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  if (p != v.size() && v[p] == a)
      |      ~~^~~~~~~~~~~
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:78:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |   if (adj_list[i].size() == V - 2)
      |       ~~~~~~~~~~~~~~~~~~~^~~~~~~~

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