Submission #207066

#	Time	Username	Problem	Language	Result	Execution time	Memory
207066		PeppaPig	Airline Route Map (JOI18_airline)	C++14	100 / 100	670 ms	30904 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;


void Alice(int n, int m, int A[], int B[]){
	vector<pii> E;
	for(int i = 0; i < m; i++) E.emplace_back(A[i], B[i]);
	for(int i = 0; i <= 9; i++) {
		for(int j = 0; j < n; j++) if(j >> i & 1)
			E.emplace_back(n + i, j);
		if(i < 9) E.emplace_back(n + i, n + i + 1);
	}
	for(int i = 0; i < n; i++) E.emplace_back(n + 10, i);
	E.emplace_back(n + 10, n + 11);

	InitG(n + 12, (int)E.size());
	for(int i = 0; i < E.size(); i++)
		MakeG(i, E[i].x, E[i].y);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e3+50;

static int n, rep;
static int is_node[N], id[N];
static vector<int> g[N];

void Bob(int n, int m, int A[], int B[]){
	for(int i = 0; i < m; i++) {
		g[A[i]].emplace_back(B[i]);
		g[B[i]].emplace_back(A[i]);
	}

	for(int i = 0; i < n; i++) if(g[i].size() == 1 && g[g[i][0]].size() == n - 11) {
		rep = g[i][0];
		for(int x : g[rep]) is_node[x] = 1;
		break;
	}
	int now = rep, pre = rep;
	for(int i = 0; i < n; i++) if(i != rep && !is_node[i] && g[i].size() <= g[now].size())
		now = i, pre = i;
	for(int i = 9; ~i; i--) {
		for(int x : g[now]) if(is_node[x])
			id[x] += 1 << i;
		for(int x : g[now]) if(!is_node[x] && x != pre) {
			pre = now, now = x;
			break;
		}
	}

	vector<pii> E;
	for(int i = 0; i < m; i++) if(is_node[A[i]] && is_node[B[i]])
		E.emplace_back(id[A[i]], id[B[i]]);
	InitMap(n - 12, (int)E.size());
	for(pii p : E) MakeMap(p.x, p.y);
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < E.size(); i++)
                 ~~^~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:22:70: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < n; i++) if(g[i].size() == 1 && g[g[i][0]].size() == n - 11) {
                                                    ~~~~~~~~~~~~~~~~~~^~~~~~~~~
Bob.cpp: At global scope:
Bob.cpp:12:12: warning: 'n' defined but not used [-Wunused-variable]
 static int n, rep;
            ^

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