Submission #1308208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308208		Zero_OP	Airline Route Map (JOI18_airline)	C++20	100 / 100	170 ms	30284 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>

using namespace std;
namespace{
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple

#define tcT template<class T

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)

tcT> bool minimize(T& a, const T& b){
	return (a > b ? a = b, 1 : 0);
}

tcT> bool maximize(T& a, const T& b){
	return (a < b ? a = b, 1 : 0);
}

tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;

using ll = long long;
using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;

using vpi = vector<pi>;
using vpl = vector<pl>;

}

void Alice( int N, int M, int A[], int B[] ){
	int LG = 10;
	
	vpi edges;
	F0R(i, LG - 1){
		edges.eb(i + N, N + i + 1);
	}

	int extraBit = N + LG;
	int extraAll = N + LG + 1;
	F0R(i, N){
		F0R(j, LG) if((i + 2) >> j & 1){
			edges.eb(i, j + N);
		}
		edges.eb(extraAll, i);
	}

	F0R(j, LG) edges.eb(extraAll, j + N), edges.eb(extraBit, j + N);
	F0R(i, M) edges.eb(A[i], B[i]);

	InitG(N + LG + 2, sz(edges));
	for(int i = 0; auto [u, v] : edges) MakeG(i++, u, v);

	// cerr << "Alice send : " << N + LG + 2 << ' ' << sz(edges) << '\n';
	// for(auto [u, v] : edges) cerr << u << ' ' << v << '\n';
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>

using namespace std;
namespace{
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple

#define tcT template<class T

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)

tcT> bool minimize(T& a, const T& b){
	return (a > b ? a = b, 1 : 0);
}

tcT> bool maximize(T& a, const T& b){
	return (a < b ? a = b, 1 : 0);
}

tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;

using ll = long long;
using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;

using vpi = vector<pi>;
using vpl = vector<pl>;

const int MAX = 1505;
int deg[MAX], degChain[MAX];
vpi edges;
vi adjChain[MAX];
}


void Bob( int V, int U, int C[], int D[] ){
	// cerr << __func__ << ' ' << V << ' ' << U << '\n';
	// F0R(i, U) cerr << C[i] << ' ' << D[i] << '\n';
	F0R(i, U){
		int u = C[i], v = D[i];
		++deg[u];
		++deg[v];
		edges.eb(u, v);
	}

	int extraAll = max_element(deg, deg + V) - deg;
	// cerr << "extraAll = " << extraAll << '\n';
	vi used(V);
	F0R(i, U){
		if(C[i] == extraAll || D[i] == extraAll){
			int x = C[i] ^ D[i] ^ extraAll;
			used[x] = 1;
		}
	}

	int extraBit = -1;
	F0R(i, V){
		if(!used[i] && i != extraAll){
			// cerr << "accept " << i << " as extraBit \n";
			// assert(extraBit == -1);
			extraBit = i;
		}
	}

	vi bitNode(V);
	int LG = 0;
	F0R(i, U){
		if(C[i] == extraBit || D[i] == extraBit){
			int x = C[i] ^ D[i] ^ extraBit;
			bitNode[x] = 1;
			++LG;
		}
	}

	// assert(LG == 10);
	F0R(i, U){
		int u = C[i], v = D[i];
		if(bitNode[u] && bitNode[v]){
			++degChain[u];
			++degChain[v];
			adjChain[u].eb(v);
			adjChain[v].eb(u);
		}
	}

	pi heads = {-1, -1};
	F0R(i, V){
		if(degChain[i] == 1){
			if(heads.ff == -1) heads.ff = i;
			else{
				// assert(heads.ss == -1);
				heads.ss = i;
			}
		}
	}

	// assert(heads.ff != -1 && heads.ss != -1);
	// assert(deg[heads.ff] != deg[heads.ss]);
	int bit0 = deg[heads.ff] > deg[heads.ss] ? heads.ff : heads.ss;

	// cerr << deg[heads.ff] << ' ' << deg[heads.ss] << '\n';
	// cerr << heads.ff << ' ' << heads.ss << " | " << bit0 << '\n';

	vi bit(V, -1);
	int u = bit0, pre = -1, cnt = 0;
	while(true){
		bit[u] = cnt++;
		if(cnt == 10) break;
		int nxt = -1;
		for(auto v : adjChain[u]) if(v != pre){
			nxt = v;
			break;
		}
		pre = u; u = nxt;
	}

	vi original(V);
	int N = V - 12;
	F0R(i, U){
		int u = C[i], v = D[i];
		if(bit[u] != -1 && bit[v] == -1){
			original[v] |= (1 << bit[u]);
		} else if(bit[u] == -1 && bit[v] != -1){
			original[u] |= (1 << bit[v]);
		}
	}

	vpi edges;
	F0R(i, U){
		int u = C[i], v = D[i];
		if(u == extraAll || v == extraAll) continue;
		if(u == extraBit || v == extraBit) continue;
		if(bit[u] != -1 || bit[v] != -1) continue;
		int x = original[u] - 2, y = original[v] - 2;
		// assert(x >= 0 && y >= 0);
		edges.eb(x, y);
	}

	int M = sz(edges);
	InitMap(N, M);
	for(auto [u, v] : edges) MakeMap(u, v); 
}

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