Submission #95845

#	Time	Username	Problem	Language	Result	Execution time	Memory
95845		diamond_duke	Airline Route Map (JOI18_airline)	C++11	100 / 100	789 ms	31580 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 + 10; i++)
		edge.emplace_back(i, n + 11);
	for (int i = 0; i < 10; i++)
		edge.emplace_back(n + i, n + 10);
	for (int i = 1; i < 10; i++)
		edge.emplace_back(n + i - 1, n + i);
	edge.emplace_back(n + 1, n + 3);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (i & (1 << j))
				edge.emplace_back(i, n + j);
		}
	}
	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 have[2005][2005], del[2005];
void dfs(int u, int rk = 0, int fa = -1)
{
	seq[rk] = u;
	for (int v : G[u])
	{
		if (v != fa)
			dfs(v, rk + 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]);
		have[eu[i]][ev[i]] = have[ev[i]][eu[i]] = true;
	}
	int n11 = -1, n10 = -1;
	for (int i = 0; i < n && -1 == n11; i++)
	{
		if (adj[i].size() == n - 2)
			n11 = i;
	}
	for (int i = 0; i < n && -1 == n10; i++)
	{
		if (i != n11 && !have[i][n11])
			n10 = i;
	}
	for (int i = 0; i < n; i++)
	{
		if (have[n10][i])
			seq.push_back(i);
	}
	for (int u : seq)
	{
		for (int v : seq)
		{
			if (have[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::find(G[u].begin(), G[u].end(), v));
			G[v].erase(std::find(G[v].begin(), G[v].end(), u));
			break;
		}
	}
	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[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[real[i]][real[j]])
				edge.emplace_back(i, j);
		}
	}
	InitMap(n - 12, edge.size());
	for (auto &it : edge)
		MakeMap(it.first, it.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:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (adj[i].size() == n - 2)
       ~~~~~~~~~~~~~~^~~~~~~~

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