Submission #1214667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214667		mychecksedad	Airline Route Map (JOI18_airline)	C++20	22 / 100	166 ms	19772 KiB

Alice

#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;

void Alice( int n, int m, int A[], int B[] ){
	vector<vector<bool>> E(n, vector<bool>(n));
	for(int i = 0; i <m; ++i) if(A[i]> B[i]) swap(A[i], B[i]); 
	for(int i = 0; i <m; ++i) E[A[i]][B[i]] = 1;


	vector<pii> P;
	for(int i = 0; i < n; ++i){
		for(int j = i + 1; j < n; ++j){
			if(E[i][j]){
				P.pb({i, j});
			}
		}
	}

	vi ID;
	for(int i = 0; i < 1024; ++i){
		if(__builtin_popcount(i) >= 2) ID.pb(i);
	}
	sort(all(ID), [&](const int &x, const int &y){
		bool a = x % 2;
		bool b = y % 2;
		if(a == b) return x < y;
		if(a) return true;
		return false; 
	});

	for(int i = 0; i < n; ++i){
		for(int j = 0; j < 10; ++j){
			if((1<<j)&ID[i]) P.pb({i, n + j});
		}
	}

	int t = n + 11;
	int s = n + 10;
	P.pb({s, t});

	for(int i = n; i < n + 10; ++i){
		P.pb({s, i});
	}

	P.pb({n + 1, n + 2});
	P.pb({n + 2, n + 3});
	P.pb({n + 2, n});
	P.pb({n + 3, n});

	for(int i = n + 5; i < n + 10; ++i){
		for(int j = n; j < i; ++j) P.pb({i, j});
	}


	int cnt = 0;
	InitG(n + 12, int(P.size()));
	for(auto [x, y]: P){
		// cerr << x << ' ' << y << '\n';
		MakeG(cnt++, x, y);
	}
}

Bob

#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


void assertt(bool b){
	if(!b){
		vi v;
		for(int i = 1; i <= MOD; ++i){
			v.pb(i);
		}
	}
}

void Bob( int nn, int mm, int C[], int D[] ){
	int n = nn - 12;
	vi deg(nn);
	vector<vector<bool>> E(nn, vector<bool>(nn));
	for(int i = 0; i < mm; ++i){
		deg[C[i]]++;
		deg[D[i]]++;
		E[C[i]][D[i]] = E[D[i]][C[i]] = 1;
	}

	int t = -1;
	for(int i = 0; i < nn; ++i){
		if(deg[i] == 1){
			if(t == -1) t = i;
		}
	}
	int s = -1;
	for(int i = 0; i < nn; ++i) if(E[t][i]) s = i;

	vi A;
	for(int i = 0; i < nn; ++i){
		if(i == s || i == t) continue;
		if(E[i][s]) A.pb(i);
	}

	vi degg(nn);
	for(int j = 0; j < 10; ++j){
		for(int i = 0; i < 10; ++i) degg[A[j]] += E[A[j]][A[i]];
	}
	sort(all(A), [&](const int &x, const int &y){
		return degg[x] < degg[y];
	});

	// 5, 2, 4, 1, 3, 6, 7, 8, 9, 10
	// 5, 2, 1, 4, 3, 6, 7, 8, 9, 10

	swap(A[2], A[4]);

	// 5, 2, 3, 4, 1, 6, 7, 8, 9, 10
	// 5, 2, 3, 1, 4, 6, 7, 8, 9, 10


	if(deg[A[3]] <= deg[A[4]]){
		swap(A[0], A[4]);
	}else{
		swap(A[3], A[4]);
		swap(A[0], A[4]);
	}


	vi node(n, -1);

	vi ID;
	for(int i = 0; i < 1024; ++i){
		if(__builtin_popcount(i) >= 2) ID.pb(i);
	}

	sort(all(ID), [&](const int &x, const int &y){
		bool a = x % 2;
		bool b = y % 2;
		if(a == b) return x < y;
		if(a) return true;
		return false; 
	});

	vi pos(1024, -1);
	for(int i = 0; i < ID.size(); ++i) pos[ID[i]] = i;	

	for(int i = 0; i < nn; ++i){
		if(i == s || i == t) continue;
		bool in = false;
		for(int x: A) in = in | (x == i);
		if(in) continue;
		int sum = 0;
		for(int j = 0; j < 10; ++j) sum += (1<<(j)) * E[i][A[j]];
		node[pos[sum]] = i;
	cerr << sum << '\n';
	}

	for(int i = 0; i < n; ++i){
		assertt(node[i] != -1);
	}

	vector<pii> P;
	for(int i = 0; i < n; ++i){
		for(int j = i + 1; j < n; ++j){
			int v = node[i], u = node[j];
			if(E[u][v]) P.pb({i, j});
		}
	}
	InitMap(n, int(P.size()));
	for(auto [x, y]: P) MakeMap(x, y);
}

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