Submission #97000

#	Time	Username	Problem	Language	Result	Execution time	Memory
97000		diamond_duke	Airline Route Map (JOI18_airline)	C++11	100 / 100	859 ms	30952 KiB

Alice

#include "Alicelib.h"
#include <utility>
#include <vector>
void Alice(int n, int m, int *eu, int *ev)
{
	std::vector<std::pair<int, int> > edge;
	for (int i = 0; i < m; i++)
		edge.emplace_back(eu[i], ev[i]);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (i & (1 << j))
				edge.emplace_back(i, n + j);
		}
	}
	for (int i = 0; i < n + 10; i++)
		edge.emplace_back(i, n + 10);
	for (int i = 0; i < 10; i++)
		edge.emplace_back(n + i, n + 11);
	for (int i = 1; i < 10; i++)
		edge.emplace_back(n + i - 1, n + i);
	edge.emplace_back(n + 1, n + 3);
	InitG(n + 12, edge.size());
	for (int i = 0; i < edge.size(); i++)
		MakeG(i, edge[i].first, edge[i].second);
}

Bob

#include "Boblib.h"
#include <algorithm>
#include <utility>
#include <vector>
std::vector<int> adj[2005], G[2005], seq;
int real[2005];
bool del[2005];
inline bool have_edge(int u, int v) { return std::binary_search(adj[u].begin(), adj[u].end(), v); }
void dfs(int u, int dep = 0, int fa = -1)
{
	seq[dep] = u;
	for (int v : G[u])
	{
		if (v != fa)
			dfs(v, dep + 1, u);
	}
}
void Bob(int n, int m, int *eu, int *ev)
{
	for (int i = 0; i < m; i++)
	{
		adj[eu[i]].push_back(ev[i]);
		adj[ev[i]].push_back(eu[i]);
	}
	for (int i = 0; i < n; i++)
		std::sort(adj[i].begin(), adj[i].end());
	int n10 = -1;
	for (int i = 0; i < n; i++)
	{
		if (adj[i].size() == n - 2)
			n10 = i;
	}
	int n11 = -1;
	for (int i = 0; i < n; i++)
	{
		if (i != n10 && !have_edge(n10, i))
			n11 = i;
	}
	seq = adj[n11];
	for (int u : seq)
	{
		for (int v : seq)
		{
			if (have_edge(u, v))
				G[u].push_back(v);
		}
	}
	int n0 = -1;
	for (int u : seq)
	{
		if (G[u].size() == 1 && G[G[u][0]].size() == 3)
			n0 = u;
	}
	for (int u : seq)
	{
		if (G[u].size() != 3)
			continue;
		for (int v : G[u])
		{
			if (G[v].size() != 3)
				continue;
			G[u].erase(std::lower_bound(G[u].begin(), G[u].end(), v));
			G[v].erase(std::lower_bound(G[v].begin(), G[v].end(), u));
		}
	}
	dfs(n0);
	for (int u : seq)
		del[u] = true;
	del[n10] = del[n11] = true;
	for (int i = 0; i < n; i++)
	{
		if (del[i])
			continue;
		int rk = 0;
		for (int j = 0; j < 10; j++)
		{
			if (have_edge(i, seq[j]))
				rk |= 1 << j;
		}
		real[rk] = i;
	}
	std::vector<std::pair<int, int> > edge;
	for (int i = 0; i < n - 12; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (have_edge(real[i], real[j]))
				edge.emplace_back(i, j);
		}
	}
	InitMap(n - 12, edge.size());
	for (int i = 0; i < edge.size(); i++)
		MakeMap(edge[i].first, edge[i].second);
}

Compilation message (stderr)

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

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (adj[i].size() == n - 2)
       ~~~~~~~~~~~~~~^~~~~~~~
Bob.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edge.size(); i++)
                  ~~^~~~~~~~~~~~~

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