Submission #648774

#	Time	Username	Problem	Language	Result	Execution time	Memory
648774		Johann	Airline Route Map (JOI18_airline)	C++14	0 / 100	822 ms	21332 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;
	// von Z := N + 10 zu allen Knoten von G
	for (int i = 0; i < N; ++i)
		edges.push_back({N + 10, i});
	// von C := N + 11 zu allen Kontrolknoten
	for (int i = 0; i < 11; ++i)
		edges.push_back({N + 11, N + i});
	// Zwischen den Count Bits (der letzte zu Z)
	for (int b = 0; b < 10; ++b)
		edges.push_back({N + b, N + b + 1});
	// für alle anderen Knoten im Graph:
	for (int v = 0; v < N; ++v)
		for (int b = 0; b < 10; ++b)
			if (v & (1 << b))
				edges.push_back({v, N + b});
	// Ausfüllen
	InitG(N + 12, M + sz(edges));
	int idx = 0;
	for (int i = 0; i < M; ++i)
		MakeG(idx++, A[i], B[i]);
	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;
	for (int u : adj[v])
	{
		if (rename[u] != -1)
			continue;
		dfs(adj, u, countBits, rename);
	}
	countBits.push_back(v);
}

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

	bool poss = false;
	int c = -1, z = -1;
	for (int cc = 0; cc < V; ++cc)
	{
		if (sz(adj[cc]) != 11)
			continue;
		for (int cz : adj[cc])
		{
			if (sz(adj[cz]) != V - 10)
				continue;
			vb nodes(V, false);
			for (int x : adj[cz])
				nodes[x] = true;
			for (int x : adj[cc])
				nodes[x] = true;
			poss = true;
			for (bool x : nodes)
				if (!x)
					poss = false;
			if (poss)
			{
				c = cc;
				z = cz;
			}
		}
		if (poss)
			break;
	}
	vi rename(V, 0);
	rename[c] = -2;
	for (int x : adj[c])
		rename[x] = -1;
	vi countBits;
	dfs(adj, z, 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 += 21; // 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], rename[u]);
	}
}

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