Submission #883141

#	Time	Username	Problem	Language	Result	Execution time	Memory
883141		NK_	Airline Route Map (JOI18_airline)	C++17	22 / 100	423 ms	47232 KiB

Alice

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "Alicelib.h"

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

#define f first
#define s second
#define mp make_pair


using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;

mt19937 rngA(time(nullptr));

vpi ordA(int N) {
	vpi B(10); for(int i = 0; i < 10; i++) {
		B[i] = mp(i, 0);
	}

	for(int i = 0; i < N; i++) {
		for(int b = 0; b < N; b++) if ((i >> b) & 1) B[b].s++;
	}

	shuffle(begin(B), end(B), rngA);

	return B;
}

const int EX = 12;
void Alice(int N, int M, int A[], int B[]){
	int EX1 = N + EX - 2;
	int EX2 = N + EX - 1;


	vpi E;

	for(int i = 0; i < M; i++) {
		E.pb(mp(A[i], B[i]));
	}

	for(int i = 0; i < N; i++) {
		for(int b = 0; b < 10; b++) if ((i >> b) & 1) {
			E.pb(mp(N + b, i));
		}
	}

	vpi ORD = ordA(N);

	// for(auto& x : ORD) cout << "( " << x.f << ", " << x.s << " ) ";
	// cout << endl;

	for(int i = 1; i < sz(ORD); i++) {
		E.pb(mp(ORD[i-1].f + N, ORD[i].f + N));
	}

	E.pb(mp(ORD.back().f + N, EX2));
	E.pb(mp(EX1, EX2));

	for(int i = 0; i < sz(ORD); i++) {
		E.pb(mp(EX1, ORD[i].f + N));
	}

	InitG(N + EX, sz(E));
	for(int i = 0; i < sz(E); i++) {
		// cout << i << " " << E[i].f << " " << E[i].s << endl;
		// if (count(begin(E), end(E), E[i]) > 1) cout << "******" << endl;

		MakeG(i, E[i].f, E[i].s);
	}
}

Bob

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "Boblib.h"

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

#define f first
#define s second
#define mp make_pair


using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;

mt19937 rngB(time(nullptr));

vpi ordB(int N) {
	vpi B(10); for(int i = 0; i < 10; i++) {
		B[i] = mp(i, 0);
	}

	for(int i = 0; i < N; i++) {
		for(int b = 0; b < N; b++) if ((i >> b) & 1) B[b].s++;
	}

	shuffle(begin(B), end(B), rngB);

	return B;
}

const int EX = 12;

void Bob(int N, int M, int A[], int B[]){
	V<vi> adj(N);
	for(int i = 0; i < M; i++) {
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}

	vpi ORD = ordB(N - EX); int K = sz(ORD);
	for(int i = 0; i < K; i++) ORD[i].s += 2 + (i != 0);

	ORD.pb(mp(-1, 2)); K++;

	// for(auto& x : ORD) cout << "( " << x.f << ", " << x.s << " ) ";
	// cout << endl;

	vi stk = {}, alive(N, 0);
	V<vi> vis(N, vi(K + 1));

	V<vi> ans;

	function<void(int, int)> find = [&](int u, int d) {
		// cout << u << " " << d << " => " << sz(adj[u]) << endl;
		stk.pb(u);
		if (d == K) {
			// cout << "FOUND" << endl;
			ans.pb(stk);
		} else {
			for(auto& v : adj[u]) if (alive[v] && count(begin(stk), end(stk), v) == 0) {
				// cout << "E: " << u << " -> " << v << " => " << sz(adj[v]) << " = " << ORD[d].s << " -> " << vis[v][d + 1] << endl;
				// cout << endl;
				if (sz(adj[v]) == ORD[d].s) {
					find(v, d + 1);
				}
			}
		}

		stk.pop_back();
	};

	for(int i = 0; i < N; i++) {
		if (sz(adj[i]) == K) {
			// cout << i << endl;
			vis[i] = vi(K + 1, 0);

			// cout << "ALIVE" << endl;
			for(auto x : adj[i]) {
				// cout << x << " ";
				alive[x] = 1; vis[x] = vi(K + 1, 0);
			}
			// cout << endl;

			find(i, 0);

			for(auto x : adj[i]) alive[x] = 0;
		}
	}

	// for(auto& x : ans) {
	// 	for(auto& v : x) cout << v << " ";
	// 	cout << endl;
	// }

	assert(sz(ans) > 0);
	// cout << sz(ans) << endl;


	vi BITS(K);	vi X(N); 
	for(auto& x : ans.front()) X[x] = -1;
	for(int i = 1; i < sz(ans.front()) - 1; i++) {
		BITS[ORD[i - 1].f] = ans.front()[i];
		// cout << ORD[i - 1].f << " " << ans.front()[i] << endl;
	}

	// for(auto& x : BITS) cout << x << " ";
	// cout << endl;

	for(int i = 0; i < K-1; i++) {
		for(auto& x : adj[BITS[i]]) {
			if (X[x] == -1) continue;
			X[x] ^= (1 << i);
		}
	}

	vpi E;

	for(int u = 0; u < N; u++) {
		int U = X[u];
		if (U == -1) continue;

		for(auto& v : adj[u]) {
			int V = X[v];
			if (V == -1) continue;

			if (U < V) {
				// cout << U << " " << V << endl;
				E.pb(mp(U, V));
			}
		}
	}

	InitMap(N - EX, sz(E));
	for(int i = 0; i < sz(E); i++) MakeMap(E[i].f, E[i].s);
}

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