Submission #219547

#	Time	Username	Problem	Language	Result	Execution time	Memory
219547		mode149256	Airline Route Map (JOI18_airline)	C++14	37 / 100	657 ms	30832 KiB

Alice

/*input

*/
#include <bits/stdc++.h>
#include "Alicelib.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

static unordered_map<int, int> sk = {
	{511, 1012},
	{767, 1013},
	{895, 1014},
	{959, 1016},
	{991, 1017},
	{1007, 1018},
	{1015, 1020},
	{1019, 1023},
	{1021, 1024},
	{1022, 1025},
};

void Alice( int N, int M, int A[], int B[] ) {
	for (int i = 0; i < N; ++i)
	{
		if (__builtin_popcount(i) != 9)
			sk[i] = i;
	}
	vpi edges;
	for (int i = 0; i < M; ++i) {
		edges.emplace_back(A[i], B[i]);
	}

	for (int i = 0; i < 9; ++i)
	{
		edges.emplace_back(N + i, N + i + 1);
	}
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < 10; ++j)
		{
			if ((sk[i] >> j) & 1)
				edges.emplace_back(i, N + j);
		}

		edges.emplace_back(N + 10, i);
	}

	for (int i = 0; i < N + 10; ++i)
		edges.emplace_back(N + 11, i);

	InitG( N + 12, (int)edges.size());

	for (int i = 0; i < (int)edges.size(); ++i)
	{
		// printf("%d %d\n", edges[i].x, edges[i].y);
		MakeG(i, edges[i].x, edges[i].y);
	}
}

Bob

/*input

*/
#include <bits/stdc++.h>
#include "Boblib.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

static unordered_map<int, int> sk = {
	{1000, 511},
	{1001, 767},
	{1002, 895},
	{1003, 959},
	{1004, 991},
	{1005, 1007},
	{1006, 1015},
	{1008, 1019},
	{1009, 1021},
	{1010, 1022},
};

void Bob( int V, int U, int C[], int D[] ) {
	// printf("IM IN BOB\n");
	int N = V - 12;
	vi kas(V, 0);
	vii edges(V);

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

	int n11 = -1;

	for (int i = 0; i < V; ++i)
	{
		if ((int)edges[i].size() == N + 10) {
			kas[i] = N + 11;
			n11 = i;
			break;
		}
	}

	int n10 = 0;
	{
		vb buvo(V, false);
		buvo[n11] = true;
		for (auto u : edges[n11])
			buvo[u] = true;

		for (int i = 0; i < V; ++i)
		{
			if (!buvo[i]) {
				n10 = i;
				kas[i] = N + 10;
			}
		}
	}

	vi pirmiN;
	// vi bitai;
	vi bit(10);

	vb bitas(V, true);
	{
		// vb buvo(V, false);
		bitas[n11] = false;
		bitas[n10] = false;
		for (auto u : edges[n10]) {
			pirmiN.emplace_back(u);
			bitas[u] = false;
		}

		vi sonai;
		for (int i = 0; i < V; ++i) {
			if (bitas[i]) {
				int cnt = 0;
				for (auto u : edges[i]) {
					if (bitas[u])
						cnt++;
				}

				if (cnt == 1)
					sonai.emplace_back(i);
			}
		}

		assert(sonai.size() == 2);
		int n0;
		if (edges[sonai[0]].size() > edges[sonai[1]].size())
			n0 = sonai[0];
		else
			n0 = sonai[1];

		kas[n0] = N + 0;
		bit[0] = n0;
		int curr = n0;
		bool ch = true;

		while (ch) {
			ch = false;
			for (auto u : edges[curr]) {
				if (bitas[u]) {
					bitas[curr] = false;
					kas[u] = kas[curr] + 1;
					bit[kas[u] - N] = u;
					curr = u;
					ch = true;
					break;
				}
			}
		}
	}

	{
		for (int i = 0; i < 10; ++i)
		{
			for (auto u : edges[bit[i]]) {
				if (kas[u] >= N) continue;

				kas[u] |= (1 << i);
			}
		}
	}
	// print(kas);
	// printf("ATS\n");
	vpi ats;
	for (int i = 0; i < U; ++i)
	{
		if (sk.count(kas[i])) kas[i] = sk[kas[i]];

		if (kas[C[i]] < N and kas[D[i]] < N) {
			// printf("%d %d\n", kas[C[i]], kas[D[i]]);
			ats.emplace_back(kas[C[i]], kas[D[i]]);
		}
	}

	InitMap( N, (int)ats.size());
	for (auto u : ats)
		MakeMap(u.x, u.y);
}

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