Submission #207195

#	Time	Username	Problem	Language	Result	Execution time	Memory
207195		nvmdava	Airline Route Map (JOI18_airline)	C++17	100 / 100	665 ms	31488 KiB

Alice

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

vector<pair<int, int> > e;

void Alice( int N, int M, int A[], int B[] ){

	for(int i = 0; i < M; ++i)
		e.push_back({A[i], B[i]});

	for(int j = 0; j < 10; ++j)
		for(int i = 0; i < N; ++i)
			if(i & (1 << j))
				e.push_back({N + j, i});
	
	for(int i = 1; i <= 9; ++i){
		for(int j = i + 1; j <= 9; ++j){
			if(i + j >= 10){
				e.push_back({N + i, N + j});
			}
		}
	}
	e.push_back({N + 0, N + 5});
	for(int i = 0; i < N + 10; ++i)
		e.push_back({N + 10, i});
	for(int i = 0; i < 10; ++i)
		e.push_back({N + 11, N + i});

	InitG(N + 12, e.size());
	int t = 0;
	for(auto& x : e)
		MakeG(t++, x.first, x.second);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define N 1505

int deg[N], id[N];

bool adj[N][N];
vector<pair<int, int> > v;

void Bob( int V, int U, int C[], int D[] ){

	for(int i = 0; i < U; ++i){
		++deg[D[i]];
		++deg[C[i]];
		adj[C[i]][D[i]] = adj[D[i]][C[i]] = 1;
	}

	int r, t;
	for(int i = 0; i < V; ++i)
		if(deg[i] == V - 2)
			r = i;
	

	for(int i = 0; i < V; ++i)
		if(r != i && !adj[r][i])
			t = i;

	id[r] = id[t] = -1;

	for(int x = 0; x < V; ++x)
		if(adj[t][x])
			v.push_back({0, x});

	for(int i = 0; i < 10; ++i){
		for(int j = 0; j < 10; ++j)
			v[i].ff += adj[v[i].ss][v[j].ss];
		id[v[i].ss] = -1;
	}
	sort(v.begin(), v.end());

	if(adj[v[0].ss][v[9].ss])
		swap(v[1], v[0]);
	if(adj[v[0].ss][v[6].ss])
		swap(v[6], v[5]);

	for(int i = 0; i < 10; ++i)
		for(int x = 0; x < V; ++x)
			if(adj[x][v[i].ss] && id[x] != -1)
				id[x] |= 1 << i;

	int cnt = 0;
	for(int i = 0; i < U; ++i){
		C[i] = id[C[i]];
		D[i] = id[D[i]];
		if(C[i] != -1 && D[i] != -1)
			++cnt;
	}
	InitMap(V - 12, cnt);
	for(int i = 0; i < U; ++i)
		if(C[i] != -1 && D[i] != -1)
			MakeMap(C[i], D[i]);
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:31:16: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  id[r] = id[t] = -1;
          ~~~~~~^~~~
Bob.cpp:31:8: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  id[r] = id[t] = -1;
  ~~~~~~^~~~~~~~~~~~

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