Submission #1214609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214609		mychecksedad	Airline Route Map (JOI18_airline)	C++20	79 / 100	172 ms	23436 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});
			}
		}
	}
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < 10; ++j){
			if((1<<j)&(i+2)) P.pb({i, n + j});
		}
	}

	int s = n + 15;
	int t = n + 16;
	for(int i = 0; i < n; ++i) P.pb({i, s});
	for(int i = 0; i < n; ++i) P.pb({i, t});
	P.pb({s, t});
	for(int i = n + 10; i < n + 15; ++i){
		P.pb({s, i});
		P.pb({t, i});
		P.pb({n, i}); // 1 - 6 identification
	}
	for(int i = 0; i < 10; ++i){
		if(i < 5) P.pb({s, n + i});
		else P.pb({t, n + i});
	}

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


	P.pb({n + 6, n + 7});
	P.pb({n + 7, n + 8});
	P.pb({n + 7, n + 9});
	P.pb({n + 8, n + 9});

	P.pb({n + 3, n + 8}); // connect 5's

	int cnt = 0;
	InitG(n + 17, 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 Bob( int nn, int mm, int C[], int D[] ){
	int n = nn - 17;
	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 s = -1, t = -1;
	for(int i = 0; i < nn; ++i){
		if(deg[i] == n + 11){
			if(s == -1) s = i;
			else t = i;
		}
	}

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

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

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

	// for(int i = 1; i <= 5; ++i){
	// 	cerr << degg[A[i - 1]] << ' ';
	// }
	
	fill(all(degg), 0);

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


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

	if(E[A[3]][B[3]]){
		// np
	}else if(E[A[3]][B[4]]){
		swap(B[3], B[4]);
	}else if(E[A[4]][B[3]]){
		swap(A[3], A[4]);
	}else{
		swap(A[3], A[4]);
		swap(B[3], B[4]);
	}

	if(deg[A[0]] < deg[B[0]]) swap(A, B);


	vi node(n, -1);

	for(int i = 0; i < nn; ++i){
		if(i == s || i == t) continue;
		bool in = false;
		for(int x: A) in = in | (x == i);
		for(int x: B) in = in | (x == i);
		if(in) continue;
		int sum = 0;
		for(int j = 0; j < 5; ++j) sum += (1<<(j)) * E[i][A[j]];
		for(int j = 5; j < 10; ++j) sum += (1<<(j)) * E[i][B[j - 5]];
		sum -= 2;
		if(sum >= 0 && sum < n){
			node[sum] = i;
		}
	}

	// for(int i = 1; i <= n; ++i){
	// 	cerr << 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});
		}
	}
	// cerr << P.size() << '\n';
	InitMap(n, int(P.size()));
	for(auto [x, y]: P) MakeMap(x, y);
}

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