Submission #1138750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138750		CDuong	Airline Route Map (JOI18_airline)	C++20	0 / 100	163 ms	19308 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

void Alice(int N, int M, int A[], int B[]) {
	vector<array<int, 2>> edge;
	for (int i = 0; i < M; ++i) {
		edge.push_back({A[i], B[i]});
	}
	for (int u = 0; u < N; ++u) for (int i = 0; i < 10; ++i) if (u >> i & 1) {
		edge.push_back({N + i, u});
	}
	for (int i = N; i < N + 10; ++i) for (int j = i + 1; j < N + 10; ++j) {
		edge.push_back({j, i});
	}
	for (int i = 0; i < N + 10; ++i) {
		edge.push_back({N + 10, i});
	}
	for (int i = N; i < N + 10; ++i) {
		edge.push_back({N + 11, i});
	}
	InitG(N + 12, isz(edge));
	for (int i = 0; i < isz(edge); ++i) {
		MakeG(i, edge[i][0], edge[i][1]);
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

void Bob(int N, int M, int A[], int B[]) {
	vector<vector<int>> g(N);
	vector a(N, vector(N, false));
	for (int i = 0; i < M; ++i) {
		int u = A[i], v = B[i];
		g[u].emplace_back(v);
		g[v].emplace_back(u);
		a[u][v] = true;
	}
	pair<int, int> mx(-1, -1);
	for (int i = 0; i < N; ++i) {
		mx = max(mx, {isz(g[i]), i});
	}
	int N10 = mx.second;
	assert(mx.first == N - 2);
	int N11 = -1, cntN10 = 0;
	for (int i = 0; i < N; ++i) if (i != N10) {
		if (not a[N10][i]) {
			N11 = i;
		}
		else {
			++cntN10;
		}
	}
	assert(cntN10 == mx.first);
	assert(N11 != -1);

	vector<int> cand = g[N11];
	assert(isz(cand) == 10);
	vector<int> cand_bit(10);
	for (int i = 0; i < 10; ++i) for (int j = 0; j < 10; ++j) {
		cand_bit[i] += a[cand[i]][cand[j]];
	}

	vector<int> vis(N);
	vis[N10] = vis[N11] = true;
	for (auto u : cand) vis[u] = true;

	vector<int> real(N);
	for (int i = 0; i < isz(cand); ++i) {
		int u = cand[i], bit = cand_bit[i];
		for (auto v : g[u]) if (not vis[v]) {
			real[v] |= 1 << bit;
		}
	}

	vector<array<int, 2>> res;
	for (int i = 0; i < M; ++i) {
		int u = A[i], v = B[i];
		if (not vis[u] and not vis[v]) {
			res.push_back({real[u], real[v]});
		}
	}

	InitMap(N - 12, isz(res));
	for (auto [u, v] : res) MakeMap(u, v);
}

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