Submission #648793

#	Time	Username	Problem	Language	Result	Execution time	Memory
648793		Johann	Airline Route Map (JOI18_airline)	C++14	100 / 100	735 ms	21392 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>

#include "bits/stdc++.h"
using namespace std;

typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()

void Alice(int N, int M, int A[], int B[])
{
	vpii edges;
	// Knoten sind 1 Indiziert...
	// von Z := 0 zu allen Knoten von G
	for (int i = 1; i <= N; ++i)
		edges.push_back({0, i});
	// Zwischen den Count Bits
	for (int b = 0; b + 1 < 10; ++b)
		edges.push_back({N + b + 1, N + b + 2});
	// Kontrollbit K = N+11 zu Z = 0
	edges.push_back({0, N + 11});
	// für alle anderen Knoten im Graph:
	for (int v = 1; v <= N; ++v)
		for (int b = 0; b < 10; ++b)
			if (v & (1 << b))
				edges.push_back({v, N + b + 1});
	// Ausfüllen
	InitG(N + 12, M + sz(edges));
	int idx = 0;
	for (int i = 0; i < M; ++i)
		MakeG(idx++, A[i] + 1, B[i] + 1);
	for (pii e : edges)
		MakeG(idx++, e.first, e.second);
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>

#include "bits/stdc++.h"
using namespace std;

typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
#define sz(x) (int)(x).size()

void dfs(vvi &adj, int v, vi &countBits, vi &rename)
{
	rename[v] = -2;
	countBits.push_back(v);
	for (int u : adj[v])
	{
		if (rename[u] == -1)
			dfs(adj, u, countBits, rename);
	}
}

void Bob(int V, int U, int C[], int D[])
{
	vvi adj(V);
	for (int i = 0; i < U; ++i)
		adj[C[i]].push_back(D[i]), adj[D[i]].push_back(C[i]);

	int k = -1;
	for (int v = 0; v < V; ++v)
		if (sz(adj[v]) == 1 && sz(adj[adj[v][0]]) == V - 11)
			// es kann maximal zwei Kandidaten sz(adj[v]) == 1 geben (k und cnt_9)
			k = v;
	int z = adj[k][0];

	vi rename(V, -1);
	for (int x : adj[z])
		rename[x] = 0;			// alle Normalen Knoten und k werden mit 0 bennant
	rename[k] = rename[z] = -2; // k wieder extra Rolle

	pii cnt0 = {-1, -1}; // { degree , node }
	for (int v = 0; v < V; ++v)
		if (rename[v] == -1) // alle Count Bits
		{
			int neighbors = 0;
			for (int x : adj[v])
				if (rename[x] == -1)
					++neighbors;
			if (neighbors == 1)
				cnt0 = max(cnt0, {sz(adj[v]), v});
		}
	vi countBits;
	dfs(adj, cnt0.second, countBits, rename);

	for (int b = 0; b < 10; ++b)
	{
		for (int v : adj[countBits[b]])
			if (rename[v] >= 0)
				rename[v] += (1 << b);
	}

	int M = 0;
	for (int v = 0; v < V; ++v)
		// Alle Kanten zwischen den Kontrollknoten und den Normalen werden enternt
		M += sz(adj[v]) * ((rename[v] >= 0) ? 1 : -1);
	M /= 2;
	M += 1 + 9; // Kanten zwischen den Knotrollknoten, müssen noch addiert werden.
	InitMap(V - 12, M);
	for (int v = 0; v < V; ++v)
	{
		if (rename[v] < 0)
			continue;
		for (int u : adj[v])
			if (rename[u] >= 0 && rename[v] > rename[u])
				MakeMap(rename[v] - 1, rename[u] - 1);
	}
}

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