Submission #57655

#	Time	Username	Problem	Language	Result	Execution time	Memory
57655		ksun48	Airline Route Map (JOI18_airline)	C++14	100 / 100	772 ms	46672 KiB

Alice

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

void send(vector<vector<int> > message){
	int V = message.size();
	int U = 0;
	for(int i = 0; i < V; i++){
		for(int j = i + 1; j < V; j++){
			if(message[i][j]){
				U++;
			}
		}
	}
	InitG(V, U);
	U = 0;
	for(int i = 0; i < V; i++){
		for(int j = i + 1; j < V; j++){
			if(message[i][j]){
				MakeG(U, i, j);
				U++;
			}
		}
	}
}

void Alice(int N, int M, int A[], int B[]){
	int L = 10;
	int n = N;
	int m = M;

	vector<vector<int> > graph(n, vector<int>(n, 0));
	vector<vector<int> > message(n + L + 2, vector<int>(n + L + 2, 0) );
	for(int i = 0; i < m; i++){
		graph[A[i]][B[i]] = graph[B[i]][A[i]] = 1;
	}

	vector<vector<int> > something(L, vector<int>(L, 0));
	for(int r = 1; r < L; r++){
		int s = r - 1;
		if(r == 4) s--;
		something[r][s] = something[s][r] = 1;
	}

	// start

	int p = n + L;
	int q = n + L + 1;
	for(int i = 0; i < p; i++){
		message[i][q] = message[q][i] = 1;
	}
	for(int i = 0; i < L; i++){
		message[n + i][p] = message[p][n + i] = 1;
	}
	for(int i = 0; i < L; i++){
		for(int a = 0; a < n; a++){
			if((1 << i) & a){
				message[a][n + i] = message[n + i][a] = 1;
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			if(graph[i][j]){
				message[i][j] = message[j][i] = 1;
			}
		}
	}
	for(int i = 0; i < L; i++){
		for(int j = 0; j < L; j++){
			if(something[i][j]){
				message[n + i][n + j] = message[n + j][n + i] = 1;
			}
		}
	}

	send(message);
}

Bob

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

void answer(vector<vector<int> > graph){
	int N = graph.size();
	int M = 0;
	for(int i = 0; i < N; i++){
		for(int j = i + 1; j < N; j++){
			if(graph[i][j]){
				M++;
			}
		}
	}
	InitMap(N, M);
	for(int i = 0; i < N; i++){
		for(int j = i + 1; j < N; j++){
			if(graph[i][j]){
				MakeMap(i, j);
			}
		}
	}
}
void Bob(int V, int U, int C[], int D[]){
	int L = 10;
	int v = V;
	int u = U;
	int n = v - L - 2;

	vector<vector<int> > graph(n, vector<int>(n, 0));
	vector<vector<int> > message(v, vector<int>(v, 0) );
	for(int i = 0; i < u; i++){
		message[C[i]][D[i]] = message[D[i]][C[i]] = 1;
	}

	vector<vector<int> > something(L, vector<int>(L, 0));
	for(int r = 1; r < L; r++){
		int s = r - 1;
		if(r == 4) s--;
		something[r][s] = something[s][r] = 1;
	}

	// start


	vector<int> degrees(v, 0);
	for(int i = 0; i < v; i++){
		for(int j = i + 1; j < v; j++){
			degrees[i] += message[i][j];
			degrees[j] += message[i][j];
		}
	}

	int q = -1;
	for(int i = 0; i < v; i++){
		if(degrees[i] == n + L){
			q = i;
		}
	}
	assert(q != -1);
	int p = -1;
	for(int i = 0; i < v; i++){
		if(i == q) continue;
		if(message[i][q] == 0){
			p = i;
		}
	}
	assert(p != -1);

	vector<int> pneighbors;
	vector<int> rest;
	for(int i = 0; i < v; i++){
		if(message[i][p] == 1){
			pneighbors.push_back(i);
		} else if(i != p & i != q){
			rest.push_back(i);
		}
	}
	assert(pneighbors.size() == L);
	assert(rest.size() == n);
	sort(pneighbors.begin(), pneighbors.end());
	while(1){
		int okay = 1;
		for(int i = 0; i < L; i++){
			for(int j = 0; j < L; j++){
				if(message[pneighbors[i]][pneighbors[j]] != something[i][j]){
					okay = 0;
					break;
				}
			}
			if(!okay) break;
		}
		if(okay) break;
		assert(next_permutation(pneighbors.begin(), pneighbors.end()));
	}

	vector<int> ids(n, 0);
	for(int i = 0; i < n; i++){
		for(int a = 0; a < L; a++){
			if(message[pneighbors[a]][rest[i]] == 1){
				ids[i] ^= (1 << a);
			}
		}
	}
	vector<int> sortedids = ids;
	sort(sortedids.begin(), sortedids.end());
	for(int i = 0; i < n; i++){
		assert(sortedids[i] == i);
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(message[rest[i]][rest[j]] == 1){
				graph[ids[i]][ids[j]] = 1;
			}
		}
	}
	answer(graph);
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:75:15: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   } else if(i != p & i != q){
             ~~^~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from Bob.cpp:2:
Bob.cpp:79:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(pneighbors.size() == L);
         ~~~~~~~~~~~~~~~~~~^~~~
Bob.cpp:80:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(rest.size() == n);
         ~~~~~~~~~~~~^~~~

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