Submission #220963

#	Time	Username	Problem	Language	Result	Execution time	Memory
220963		patrikpavic2	Airline Route Map (JOI18_airline)	C++17	100 / 100	791 ms	75096 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int N = 1055;
const int M = N * N;

typedef pair < int, int > pii;

int nnn, imaa[M], uk = 0, encode[N][N], koliko = 0;
int decodeA[M], decodeB[M];
vector < pii > bezveze;
int glp[N][N];
vector < int > v2;

void jako_glupo(){
	srand(123);
	for(int i = 0;i < 12;i++)
		for(int j = i + 1;j < 12;j++){
			glp[i][j] = glp[j][i] = rand() % 2;
			//if(glp[i][j]) printf("%d --- %d\n", i, j);
		}
}

void precompute(){
	for(int i = 0;i < nnn;i++){
		for(int j = i + 1;j < nnn;j++){
			encode[i][j] = koliko;
			encode[j][i] = koliko;
			decodeA[koliko] = i;
			decodeB[koliko] = j;
			koliko++;
		}
	}
}	

void zakompliciraj(){
	srand(69);
	for(int i = 0;i < 2 * koliko;i++){
		v2.PB(rand() % koliko); v2.PB(rand() % koliko);
	}
	for(int i = 0;i < 4 * koliko;i += 2){
		swap(imaa[v2[i]], imaa[v2[i + 1]]);
	}
	v2.clear();
}

void Alice( int nn, int mm, int A[], int B[] ){
	nnn = nn; precompute(); jako_glupo();
	for(int i = 0;i < mm;i++)
		imaa[encode[A[i]][B[i]]] = 1;
	zakompliciraj();
	for(int i = 0;i < nn * nn;i++){
		if(imaa[i]) bezveze.PB({decodeA[i], decodeB[i]});
	}
	for(int i = nn;i < nn + 12;i++){
		for(int j = 0;j < nn;j++){
			if((j & (1 << (i - nn))))
				bezveze.PB({i, j});
		}
		for(int j = 0;j < i - nn;j++){
			if(glp[i - nn][j])
				bezveze.PB({i, j + nn});
		}
	}
	InitG(nn + 12, (int)bezveze.size());
	for(int i = 0;i < (int)bezveze.size();i++){
		//printf("%d --- %d\n", bezveze[i].X, bezveze[i].Y);
		MakeG(i, bezveze[i].X, bezveze[i].Y);
	}
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;

const int N = 1055;
const int M = N * N;

int n2, m2, n, m, ima[M], spj[N][N], glp2[N][N];
int trb[N], poseban[N], prav[N];
int cur[N], tko[N], gotov = 0, poten[N], deg[N];
int encode2[N][N], koliko2;
int decodeA2[M], decodeB2[M];

vector < int > kand[N], v;

void jako_glupo2(){
	srand(123);
	for(int i = 0;i < 12;i++)
		for(int j = i + 1;j < 12;j++){
			glp2[i][j] = glp2[j][i] = rand() % 2;
			//if(glp2[i][j]) printf("%d --- %d\n", i, j);
		}
}

void precompute2(){
	for(int i = 0;i < n;i++){
		for(int j = i + 1;j < n;j++){
			encode2[i][j] = koliko2;
			encode2[j][i] = koliko2;
			decodeA2[koliko2] = i;
			decodeB2[koliko2] = j;
			koliko2++;
		}
	}
}	

void zakompliciraj_obrnuto(){
	srand(69);
	for(int i = 0;i < 2 * koliko2;i++){
		v.PB(rand() % koliko2); v.PB(rand() % koliko2);
	}
	reverse(v.begin(), v.end());
	for(int i = 0;i < 4 * koliko2;i += 2){
		swap(ima[v[i]], ima[v[i + 1]]);
	}
	v.clear();
}

void probaj(int i){
	if(i == 12){
		gotov = 1; return;
	}
	for(int x : kand[i]){
		if(poseban[x]) continue;
		int mogu = 1;
		for(int j = 0;j < i;j++)
			if(spj[x][tko[j]] != glp2[i][j])
				mogu = 0;
		if(!mogu) continue;
		tko[i] = x; poseban[x] = 1; poten[x] = i;
		probaj(i + 1);
		if(gotov) return;
		poseban[x] = 0;
	}
}

void Bob( int nn, int mm, int C[], int D[] ){
	n2 = nn; n = nn - 12; precompute2(); jako_glupo2();
	for(int i = 0;i < 12;i++){
		for(int j = 0;j < n;j++)
			trb[i] += !!(j & (1 << i));
		for(int j = 0;j < 12;j++)
			trb[i] += glp2[i][j];
	}
	for(int i = 0;i < mm;i++){
		deg[C[i]]++, deg[D[i]]++;
		//printf("%d --- %d\n", C[i], D[i]);
		spj[C[i]][D[i]] = 1; spj[D[i]][C[i]] = 1;
	}
	for(int i = 0;i < n2;i++){
		for(int j = 0;j < 12;j++){
			if(deg[i] == trb[j])
				kand[j].PB(i);// printf("%d kandidat za %d\n", i, j);
		}
	}
	probaj(0); //printf("gotov = %d\n", gotov);
	for(int i = 0;i < 12;i++)
		kand[i].clear();
	for(int i = 0;i < n2;i++){
		if(!poseban[i]) continue;
		//printf("POSEBAN : %d je %d\n", i, poten[i]);
		for(int j = 0;j < n2;j++){
			if(spj[i][j]) 
				prav[j] += (1 << poten[i]);
		}
	}
	for(int j = 0;j < n2;j++){
		if(poseban[j]) continue;
		//printf("%d ---> %d\n", j, prav[j]);
	}
	int uk = 0;
	for(int i = 0;i < mm;i++){
		if(poseban[C[i]]) continue;
		if(poseban[D[i]]) continue;
		ima[encode2[prav[C[i]]][prav[D[i]]]] = 1;
		//printf("%d --- %d tj. %d --- %d\n",C[i], D[i],prav[C[i]], prav[D[i]]);
		uk++;
	}
	zakompliciraj_obrnuto();
	InitMap(n, uk);
	for(int i = 0;i < M;i++){
		if(ima[i]) {
			//printf("spajam %d i %d\n", decodeA2[i], decodeB2[i]);
			MakeMap(decodeA2[i], decodeB2[i]); 
		}
	}
}

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