Submission #503987

#	Time	Username	Problem	Language	Result	Execution time	Memory
503987		zhougz	Airline Route Map (JOI18_airline)	C++17	Compilation error	0 ms	0 KiB

Alice

#include "alice.h"

#include <bits/stdc++.h>

using namespace std;

void Alice(int n, int m, int *a, int *b) {
	vector<pair<int, int>> res;
	for (int i = 0; i < m; i++) {
		res.emplace_back(a[i], b[i]);
	}
	for (int i = 0; i < 9; i++) {
		res.emplace_back(n + i, n + i + 1);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= 9; j++) {
			if (((i + 1) >> j) & 1) {
				res.emplace_back(i, n + j);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		res.emplace_back(i, n + 10);
	}
	res.emplace_back(n + 10, n + 11);
	InitG(n + 12, res.size());
	for (const auto &[u, vv] : res) {
		static int i = 0;
		MakeG(i++, u, vv);
	}
}

/**
 * Use the following setup:
 * 1-10: bit nodes linked together
 * 11: connect to all normal nodes (N + 1) connections
 * 12: connect only to 11th node (1) connection
 * To identify the 11th node, we identify a node with 1 connection and that neighbour is size N + 1.
 * It has to be the 12th node. Assume it is not. It can only be a
 * bit 9 node (other bit nodes have 2 neighbouring bit nodes) (bit 0 has 1 to bit 1, >= 1 to normal nodes)
 * (11th node has >= 1 + 1 connections) (normal nodes have 1 to 11th node, >= 1 to bit node)
 * Then bit 8 has N + 1 connections (2 connections to bit 7/9, N - 1 with the N normal nodes). Absurd. (#1, #2 already have unset bit 8 thus connections already <= N - 2)
 */

Bob

#include "bob.h"

#include <bits/stdc++.h>

using namespace std;

// FUCK YOU BOB WHY ZERO-INDEXED
// GIVE FUCKING BOBS TO ALICE
void Bob(int n, int m, int *a, int *b) {
	vector<vector<int>> v(n);
	for (int i = 0; i < m; i++) {
		v[a[i]].push_back(b[i]);
		v[b[i]].push_back(a[i]);
	}
	int fuck;
	for (int i = 0; i < n; i++) {
		if (v[i].size() == 1 && (int)v[v[i][0]].size() == n - 11) {
			fuck = i;
			break;
		}
	}
	unordered_set<int> bad;
	for (int i = 0; i < n; i++) {
		bad.insert(i);
	}
	for (auto x : v[v[fuck][0]]) {
		bad.erase(x);
	}
	bad.erase(v[fuck][0]);
	// By bob-force bit-0 node is always bigger than bit-9 node
	int bob, sz = 0;
	for (auto x : bad) {
		int cnt = 0;
		for (auto u : v[x]) {
			cnt += bad.find(u) != bad.end();
		}
		if (cnt == 1 && (int)v[x].size() > sz) {
			bob = x;
			sz = v[x].size();
		}
	}
	vector<bool> used(1024);
	vector<int> idx(n);
	for (int i = 0, nxt_bob; i <= 9; i++) {
		for (auto x : v[bob]) {
			if (bad.find(x) == bad.end()) {
				idx[x] += 1 << i;
			} else if (!used[x]) {
				nxt_bob = x;
			}
		}
		used[bob] = true;
		bob = nxt_bob;
	}
	vector<pair<int, int>> res;
	for (int i = 0; i < m; i++) {
		if (idx[a[i]] != 0 && idx[b[i]] != 0) {
			res.emplace_back(idx[a[i]] - 1, idx[b[i]] - 1);
		}
	}
	InitMap(n - 12, res.size());
	for (const auto &[u, vv] : res) {
		MakeMap(u, vv);
	}
}

Compilation message (stderr)

Alice.cpp:1:10: fatal error: alice.h: No such file or directory
    1 | #include "alice.h"
      |          ^~~~~~~~~
compilation terminated.

Bob.cpp:1:10: fatal error: bob.h: No such file or directory
    1 | #include "bob.h"
      |          ^~~~~~~
compilation terminated.