Submission #296749

#	Time	Username	Problem	Language	Result	Execution time	Memory
296749		Plurm	Airline Route Map (JOI18_airline)	C++11	22 / 100	668 ms	49336 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

int vg[1024][1024]; // virtual graph
void Alice( int N, int M, int A[], int B[] ){
	for(int i = 0; i < M; i++){
		if(A[i] > B[i]) swap(A[i], B[i]);
		vg[A[i]][B[i]] = 1;
	}
	for(int i = 0; i < N; i++){
		vg[i][N] = 1;
		for(int b = 0; b < 10; b++){
			if(i & (1 << b)){
				vg[i][N+1+b] = 1;
			}
		}
	}
	for(int i = 0; i < 5; i++){
		for(int j = 0; j < i; j++){
			vg[N+1+i][N+6+j] = 1;
		}
		vg[N+1+i][N+11] = 1;
	}
	vg[0][N+11] = 1;
	if(N <= 10){
		for(int i = N+12; i <= 100; i++){
			vg[N][i] = 1;
		}
	}
	vector<pair<int,int> > ev;
	const int V = N <= 10 ? 100 : N+12;
	for(int i = 0; i < V; i++){
		for(int j = i+1; j < V; j++){
			if(vg[i][j]) ev.emplace_back(i,j);
		}
	}
	InitG(V, ev.size());
	for(int i = 0; i < ev.size(); i++){
		int x, y;
		tie(x, y) = ev[i];
		MakeG(i, x, y);
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

static int bvg[1555][1555];
static bool isOriginal[1555];
static int p[1555];
void Bob( int V, int U, int C[], int D[] ){
	int N = 0;
	memset(bvg, 0, sizeof(bvg));
	memset(isOriginal, 0, sizeof(isOriginal));
	memset(p, 0, sizeof(p));
	for(int i = 0; i < U; i++){
		bvg[C[i]][D[i]] = bvg[D[i]][C[i]] = 1;
	}
	for(int i = 0; i < V; i++){
		int chc = 0;
		for(int j = 0; j < V; j++) if(bvg[i][j]) chc++;
		if(chc == 1) continue;
	}
	int SIG = -1;
	int mx = -1;
	for(int i = 0; i < V; i++){
		isOriginal[i] = true;
		int cnt = 0;
		for(int j = 0; j < V; j++){
			cnt += bvg[i][j];
		}
		if(cnt > mx){
			SIG = i;
			mx = cnt;
		}
	}
	isOriginal[SIG] = false;
	vector<int> bits;
	for(int i = 0; i < V; i++){
		if(bvg[SIG][i] == 0 && i != SIG){
			bits.push_back(i);
			isOriginal[i] = false;
		}
	}
	int BSIG = -1;
	int ZERO = -1;
	for(int i : bits){
		int chco = 0;
		int chci = 0;
		for(int j = 0; j < V; j++) if(bvg[i][j]) chco++;
		for(int j : bits) if(bvg[i][j]) chci++;
		if(chco == 6 && chci == 5) BSIG = i;
	}
	for(int i = 0; i < V; i++){
		if(bvg[SIG][i] && bvg[i][BSIG]){
			ZERO = i;
		}
	}
	bvg[BSIG][ZERO] = bvg[ZERO][BSIG] = 0;
	bits.erase(find(bits.begin(), bits.end(), BSIG));
	isOriginal[ZERO] = true;
	vector<int> leftbits, rightbits;
	for(int i : bits){
		if(bvg[BSIG][i]) leftbits.push_back(i);
		else rightbits.push_back(i);
		bvg[BSIG][i] = bvg[i][BSIG] = 0;
		int chc = 0;
		for(int j : bits) if(bvg[i][j]) chc++;
	}
	sort(leftbits.begin(), leftbits.end(), [&bits](int b1, int b2){
		int chc1 = 0;
		int chc2 = 0;
		for(int i : bits) if(bvg[b1][i]) chc1++;
		for(int i : bits) if(bvg[b2][i]) chc2++;
		return chc1 < chc2;
	});
	sort(rightbits.begin(), rightbits.end(), [&bits](int b1, int b2){
		int chc1 = 0;
		int chc2 = 0;
		for(int i : bits) if(bvg[b1][i]) chc1++;
		for(int i : bits) if(bvg[b2][i]) chc2++;
		return chc1 > chc2;
	});
	bits = leftbits;
	for(int x : rightbits) bits.push_back(x);
	for(int i = 0; i < 10; i++){
		p[bits[i]] = N+1+i;
	}
	for(int i = 0; i < V; i++){
		if(isOriginal[i] && i != ZERO){
			int name = 0;
			for(int j = 0; j < 10; j++){
				if(bvg[i][bits[j]]) name += 1 << j;
			}
			p[i] = name;
			if(name == 0) isOriginal[i] = false;
			else N++;
		}else if(i == ZERO) N++;
	}
	vector<pair<int,int> > ev;
	for(int i = 0; i < U; i++){
		if(isOriginal[C[i]] && isOriginal[D[i]]){
			ev.emplace_back(p[C[i]], p[D[i]]);
		}
	}
	InitMap(N, ev.size());
	for(auto p : ev){
		MakeMap(p.first, p.second);
	}
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0; i < ev.size(); i++){
      |                 ~~^~~~~~~~~~~

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