Submission #694138

#	Time	Username	Problem	Language	Result	Execution time	Memory
694138		jeroenodb	Airline Route Map (JOI18_airline)	C++14	100 / 100	775 ms	29372 KiB

Alice

#include "Alicelib.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
const static pi g[] = {{0,1},{1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{7,8},{8,9},{1,3}};
void Alice( int N, int M, int A[], int B[] ){
	
	int lg = 10;
	int V = lg+N+2;
	vector<pi> es;
	for(int i=0;i<M;++i) {
		es.emplace_back(A[i],B[i]);
	}
	for(int i=0;i<V-2;++i) es.emplace_back(i,V-1);
	for(int i=N;i<N+lg;++i) es.emplace_back(i,V-2);
	for(auto& [u,v] : g) es.emplace_back(u+N,v+N);
	for(int i=0;i<lg;++i) {
		
		for(int j=0;j<N;++j) if(j & (1<<i)) {
			es.emplace_back(i+N,j);
		}
	}

	InitG(N+lg+2,es.size());
	int id=0;
	for(auto& [u,v] : es) {
		MakeG(id++,u,v);
	}
}

Bob

#include "Boblib.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define all(x) begin(x),end(x)
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const static pi gg[] = {{0,1},{1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{7,8},{8,9},{1,3}};
void Bob( int V, int U, int C[], int D[] ){
	int N=V-12;
	vvi adj(V);
	for(int i=0;i<U;++i) adj[C[i]].push_back(D[i]),adj[D[i]].push_back(C[i]);
	int special = 0;
	for(int i=0;i<V;++i) if(adj[i].size()>adj[special].size()) special=i;
	int who=0;
	for(int i=0;i<V;++i) who^=i;
	who^=special;

	for(int to : adj[special]) who^=to;
	// have who, it should point exactly at the bits

	vector<bool> spec(V);
	spec[who]=spec[special]=1;
	vi bits;
	for(int to : adj[who]) {
		if(to!=special) bits.push_back(to);
		spec[to]=1;
	}
	// ok found the bits, recover order from non-isomorphic graph
	sort(all(bits));
	assert(bits.size()==10);
	vector<pi> bites;
	for(int i=0;i<10;++i) for(int to : adj[bits[i]]) {
		auto it = lower_bound(all(bits),to);
		if(it!=bits.end() and *it==to) {
			int v= it-bits.begin();
			if(i<v) bites.push_back({i,v});
		}
	}
	array<int,10> p; iota(all(p),0);
	sort(all(bites));
	do {
		bool bad=0;
		for(auto& [u,v] : gg) {
			pi want = minmax(p[u],p[v]);
			if(!binary_search(all(bites),want)) {
				bad=true;
				break;
			}
		}
		if(!bad) break;
	} while(next_permutation(all(p)));
	vi label(V);
	for(int i=0;i<10;++i) {
		for(int to : adj[bits[p[i]]]) if(!spec[to]) {
			label[to]|=1<<i;
		}
	}
	vector<pi> es;
	for(int i=0;i<U;++i) if(!spec[C[i]] and !spec[D[i]]) {
		es.emplace_back(label[C[i]],label[D[i]]);
	}
	InitMap(N,es.size());
	for(auto [u,v] : es) MakeMap(u,v);
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:24:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |  for(auto& [u,v] : g) es.emplace_back(u+N,v+N);
      |            ^
Alice.cpp:34:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |  for(auto& [u,v] : es) {
      |            ^

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:45:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |   for(auto& [u,v] : gg) {
      |             ^
Bob.cpp:65:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |  for(auto [u,v] : es) MakeMap(u,v);
      |           ^

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