Submission #336493

#	Time	Username	Problem	Language	Result	Execution time	Memory
336493		amoo_safar	Airline Route Map (JOI18_airline)	C++17	100 / 100	1464 ms	61340 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back

using namespace std;

const int Log = 10;

typedef pair<int, int> pii;

int bad[1 << Log];
vector<int> Good;

void FillBad(){
	memset(bad, 0, sizeof bad);
	bad[0] = 1;
	for(int i = 0; i < Log; i++)
		bad[1 << i] = 1;
	for(int i = 0; i + 1 < Log; i++)
		bad[3 << i] = 1;
	for(int i = 0; i < (1 << Log); i++)
		if(!bad[i])
			Good.pb(i);
}

vector<pii> E;
void Alice(int n, int m, int A[], int B[]){
	FillBad();
	E.clear();
	for(int i = 0; i < m; i++) E.pb({A[i], B[i]});
	///
	for(int i = n; i < n + 9; i++) E.pb({i, i + 1});
	for(int i = n; i <= n + 9; i++) E.pb({n + 10, i});
	E.pb({n + 11, n + 10}); E.pb({n + 11, n + 9});
	///
	assert((int) Good.size() >= n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < Log; j++){
			if(Good[i] >> j & 1)
				E.pb({n + j, i});
		}
	}

	m = E.size();
	InitG( n + 12, m);
	for(int i = 0; i < m; i++)
		MakeG(i, E[i].F, E[i].S);
	return ;
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back

using namespace std;

const int Log = 10;

typedef pair<int, int> pii;

const int N = 2e3;

int bad2[1 << Log];
vector<int> GD;

void FillBad2(){
	memset(bad2, 0, sizeof bad2);
	bad2[0] = 1;
	for(int i = 0; i < Log; i++)
		bad2[1 << i] = 1;
	for(int i = 0; i + 1 < Log; i++)
		bad2[3 << i] = 1;
	for(int i = 0; i < (1 << Log); i++)
		if(!bad2[i])
			GD.pb(i);
}



vector<int> G[N];
map<pii, int> mp;
void AddEdge(int u, int v){
	mp[{min(u, v), max(u, v)}] = 1;
	G[u].pb(v);
	G[v].pb(u);
}
bool IsEdge(int u, int v){
	return mp.count({min(u, v), max(u, v)}) > 0;
}


int deg[N];
int mk[N];
int n, m;
int FindCommon(int u, int v){
	for(int i = 0; i < n; i++){
		if(!mk[i] && IsEdge(u, i) && IsEdge(v, i))
			return i;
	}
	return -1;
}

int cntCommon(int u, int v){
	int res = 0;
	for(int i = 0; i < n; i++){
		if(!mk[i] && IsEdge(u, i) && IsEdge(v, i))
			res ++;
	}
	return res;
}

int ord[N];

int val[N];

void Bob(int V, int U, int C[], int D[] ){
	n = V; m = U;
	FillBad2();

	for(int i = 0; i < U; i++){
		AddEdge(C[i], D[i]);
		deg[C[i]] ++;
		deg[D[i]] ++;
	}
	int idx = -1;
	for(int i = 0; i < V; i++)
		if(deg[i] == 2 && IsEdge(G[i][0], G[i][1])){
			assert(idx == -1);
			idx = i;
		}
	assert(idx != -1);
	vector<int> adj;
	for(int i = 0; i < m; i++){
		if(C[i] == idx)
			adj.pb(D[i]);
		if(D[i] == idx)
			adj.pb(C[i]);
	}
	assert(adj.size() == 2);

	mk[idx] = 1;
	int X = FindCommon(adj[0], adj[1]);
	mk[adj[0]] = mk[adj[1]] = 1;

	int Y = -1;
	if(deg[adj[0]] != 11){
		Y = adj[1];
	} else if(deg[adj[1]] != 11){
		Y = adj[0];
	} else {
		if(cntCommon(X, adj[0]) != 1)
			Y = adj[1];
		if(cntCommon(X, adj[1]) != 1)
			Y = adj[0];
	}
	assert(Y != -1);
	// int Y = (FindCommon(adj[0], X) == -1 ? adj[1] : adj[0]);

	memset(mk, 0, sizeof mk);
	mk[idx] = 1; mk[Y] = 1;
	int la = idx;
	for(int i = 0; i < 10; i++){
		int com = FindCommon(la, Y);

		assert(com != -1);
		ord[com] = 9 - i;
		mk[com] = 1;
		la = com;
	}
	for(int i = 0; i < n; i++){
		if(mk[i]) continue;
		int res = 0;
		// cerr << "# ";
		for(auto nei : G[i]){
			if(mk[nei]){
				res += (1 << ord[nei]);
				// cerr << ord[nei] << ' ';
			}
		}
		// cerr << '\n';
		val[i] = lower_bound(GD.begin(), GD.end(), res) - GD.begin();
		// cerr << "! " << n << " " << res << '\n';
	}
	vector<pii> E;
	for(int i = 0; i < m; i++){
		if(mk[C[i]] || mk[D[i]]) continue;
		E.pb({val[C[i]], val[D[i]]});
	}
	InitMap( n - 12, E.size());
	for(auto [u, v] : E)

		MakeMap(u, v);
}

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