Submission #943123

#	Time	Username	Problem	Language	Result	Execution time	Memory
943123		siewjh	Airline Route Map (JOI18_airline)	C++17	100 / 100	540 ms	40196 KiB

Alice

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

void Alice(int N, int M, int A[], int B[]){
	vector<pair<int, int>> elist;
	for (int i = 0; i < M; i++) elist.push_back({A[i], B[i]});
	for (int i = 0; i < N; i++)
		for (int k = 0; k < 10; k++)
			if (i & (1 << k))
				elist.push_back({i, N + k});
	for (int k = 1; k < 10; k++) elist.push_back({N + k - 1, N + k});
	for (int k = 0; k < 10; k++) elist.push_back({N + 10, N + k});
	for (int i = 0; i < N + 10; i++) elist.push_back({N + 11, i});
	InitG(N + 12, elist.size());
	for (int i = elist.size() - 1; i >= 0; i--) MakeG(i, elist[i].first, elist[i].second);
}

Bob

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

void Bob(int V, int U, int C[], int D[]){
	vector<vector<int>> adj(V);
	vector<vector<bool>> mat(V, vector<bool>(V, 0));
	for (int i = 0; i < U; i++){
		adj[C[i]].push_back(D[i]);
		adj[D[i]].push_back(C[i]);
		mat[C[i]][D[i]] = mat[D[i]][C[i]] = 1;
	}
	int glob;
	for (int i = 0; i < V; i++)
		if (adj[i].size() == V - 2){
			glob = i;
			break;
		}
	int idc;
	for (int i = 0; i < V; i++)
		if (i != glob && !mat[glob][i]){
			idc = i;
			break;
		}
	vector<int> norm, mask;
	for (int i = 0; i < V; i++){
		if (i == glob || i == idc) continue;
		if (mat[idc][i]) mask.push_back(i);
		else norm.push_back(i);
	}
	vector<int> mv(10);
	vector<vector<int>> madj(V);
	for (int i = 0; i < 10; i++)
		for (int j = i + 1; j < 10; j++)
			if (mat[mask[i]][mask[j]]){
				madj[mask[i]].push_back(mask[j]);
				madj[mask[j]].push_back(mask[i]);
			}
	vector<int> deg1;
	for (int x : mask)
		if (madj[x].size() == 1)
			deg1.push_back(x);
	mv[0] = (adj[deg1[0]].size() > adj[deg1[1]].size() ? deg1[0] : deg1[1]);
	for (int k = 0; k < 9; k++){
		if (k == 0) mv[k + 1] = madj[mv[k]][0];
		else mv[k + 1] = (madj[mv[k]][0] != mv[k - 1] ? madj[mv[k]][0] : madj[mv[k]][1]);
	}
	int N = V - 12;
	vector<int> rev(V);
	for (int x : norm){
		int val = 0;
		for (int k = 0; k < 10; k++)
			if (mat[x][mv[k]])
				val += (1 << k);
		rev[x] = val;
	}
	vector<pair<int, int>> elist;
	for (int i = 0; i < N; i++)
		for (int j = i + 1; j < N; j++)
			if (mat[norm[i]][norm[j]])
				elist.push_back({rev[norm[i]], rev[norm[j]]});
	InitMap(N, elist.size());
	for (auto &[a, b] : elist) MakeMap(a, b); 
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:15:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |   if (adj[i].size() == V - 2){
      |       ~~~~~~~~~~~~~~^~~~~~~~
Bob.cpp:21:29: warning: 'glob' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |   if (i != glob && !mat[glob][i]){
      |                             ^
Bob.cpp:27:17: warning: 'idc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |   if (i == glob || i == idc) continue;
      |       ~~~~~~~~~~^~~~~~~~~~~

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