Submission #1028390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028390		Antekb	Airline Route Map (JOI18_airline)	C++17	100 / 100	413 ms	29688 KiB

Alice

#pragma GCC optimize("O3")
#include "bits/stdc++.h"	/** keep-include */
using namespace std;

#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto &operator<<(auto &o, pair<auto, auto> p) {
	return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
	o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
	return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
	((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif

#include "Alicelib.h"

void Alice( int n, int m, int A[], int B[] ){
	vector<pii> edg;
	for(int i=0; i<m; i++){
		deb("Alice", A[i], B[i]);
		edg.pb(mp(A[i], B[i]));
	}
	int full=n;
	int bit_ptr=n+1;
	int bits_beg=n+2;
	int bits=10;
	for(int i=0; i<n; i++){
		edg.pb(mp(full, i));
		for(int j=0; j<bits; j++){
			if(i&(1<<j)){
				edg.pb(mp(i, bits_beg+j));
			}
		}
	}
	edg.pb(mp(bits_beg, bits_beg+2));
	edg.pb(mp(bits_beg, bits_beg+3));
	for(int j=0; j<bits; j++){
		if(j>1)edg.pb(mp(bits_beg+j-1, bits_beg+j));
		edg.pb(mp(full, bits_beg+j));
		edg.pb(mp(bit_ptr, bits_beg+j));
	}
	InitG( bits_beg+bits, edg.size() );
	for(int i=0; i<SZ(edg); i++){
		MakeG(i, edg[i].st, edg[i].nd );
	}
}

Bob

#pragma GCC optimize("O3")
#include "bits/stdc++.h"	/** keep-include */
using namespace std;

#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto &operator<<(auto &o, pair<auto, auto> p) {
	return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
	o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
	return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
	((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif

#include "Boblib.h"

vector<int> get_bits(vector<vi> &E, vi V){
	int k=V.size();
	vector<vi> E2(k);
	assert(k==10);
	for(int i=0; i<k; i++){
		for(int j=0; j<k; j++){
			if(find(all(E[V[i]]), V[j])!=E[V[i]].end()){
				E2[i].push_back(j);
			}
		}
	}
	vi deg3;
	for(int i=0; i<k; i++){
		if(E2[i].size()==3)deg3.pb(i);
	}
	assert(deg3.size()==2);
	vi ans(k, -1);
	for(int i=0; i<k; i++){
		if(binary_search(all(E2[i]), deg3[0]) && binary_search(all(E2[i]), deg3[1])){
			assert(ans[0]==-1);
			ans[0]=i;
		}
	}
	assert(ans[0]!=-1);
	E2[deg3[0]].erase(find(all(E2[deg3[0]]), ans[0]));
	E2[deg3[1]].erase(find(all(E2[deg3[1]]), ans[0]));
	E2[deg3[0]].erase(find(all(E2[deg3[0]]), deg3[1]));
	E2[deg3[1]].erase(find(all(E2[deg3[1]]), deg3[0]));
	if(E2[E2[deg3[0]][0]].size()==2){
		assert(E2[E2[deg3[1]][0]].size()==1);
		swap(deg3[0], deg3[1]);
	}
	ans[1]=E2[deg3[0]][0];
	ans[2]=deg3[0];
	ans[3]=deg3[1];
	for(int i=3; i<k-1; i++){
		E2[E2[ans[i]][0]].erase(find(all(E2[E2[ans[i]][0]]), ans[i]));
		assert(E2[ans[i]].size()==1);
		ans[i+1]=E2[ans[i]][0];
	}
	for(int &i:ans){
		i=V[i];
	}
	return ans;
}

void Bob( int n, int m, int A[], int B[] ){
	vector<vector<int> > E(n);
	for(int i=0; i<m; i++){
		E[A[i]].pb(B[i]);
		E[B[i]].pb(A[i]);
		deb("Bob", A[i], B[i]);
	}
	int full=-1;
	int bit_ptr=-1;
	for(int i=0; i<n; i++){
		if(SZ(E[i])==n-2){
			sort(all(E[i]));
			int cand=-1;
			for(int j=0; j<n; j++){
				if(j!=i && !binary_search(all(E[i]), j)){
					assert(cand==-1);
					cand=j;
				}
			}
			if(SZ(E[cand])==10){
				assert(full==-1);
				full=i;
				bit_ptr=cand;
			}
		}
	}
	deb(full, bit_ptr);
	assert(full!=-1);
	vector<int> bits=get_bits(E, E[bit_ptr]);
	deb(bits);

	vector<int> labels(n);
	for(int i:bits)labels[i]=-1;
	for(int i=0; i<m; i++){
		if(labels[A[i]]==-1 && labels[B[i]]==-1){
			deb(A[i], B[i]);
		}
	}
	labels[full]=-1;
	labels[bit_ptr]=-1;
	for(int i=0; i<n; i++){
		if(labels[i]!=-1){
			sort(all(E[i]));
			for(int j=0; j<SZ(bits); j++){
				if(binary_search(all(E[i]), bits[j]))labels[i]+=(1<<j);
			}
		}
	}
	vector<pii> edg;
	for(int i=0; i<n; i++){
		if(labels[i]==-1)continue;
		for(int j:E[i]){
			if(labels[j]!=-1 && j<i){
				edg.pb(mp(labels[i], labels[j]));
			}
		}
	}
	for(auto &[x, y]:edg){
		deb(x, y);
	}
	InitMap( n-SZ(bits)-2, SZ(edg) );
	for(auto &[x, y]:edg){
		MakeMap( x, y );
	}

}

Compilation message (stderr)

Alice.cpp:18:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                  ^~~~
Alice.cpp:18:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                ^~~~
Alice.cpp:18:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                      ^~~~
Alice.cpp:20:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                 ^~~~
Alice.cpp:20:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                          ^~~~

Bob.cpp:18:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                  ^~~~
Bob.cpp:18:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                ^~~~
Bob.cpp:18:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                      ^~~~
Bob.cpp:20:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                 ^~~~
Bob.cpp:20:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                          ^~~~
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:135:12: warning: unused structured binding declaration [-Wunused-variable]
  135 |  for(auto &[x, y]:edg){
      |            ^~~~~~

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