Submission #260431

#	Time	Username	Problem	Language	Result	Execution time	Memory
260431		youngyojun	Airline Route Map (JOI18_airline)	C++17	100 / 100	1218 ms	31008 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef pair<int, int> pii;
 
static vector<pii> V;
 
void Alice( int N, int M, int A[], int B[] ){
	for(int i = 0; i < M; i++) V.eb(A[i], B[i]);
	for(int i = 0; i < N; i++)
		for(int j = 0; j < 10; j++)
			if(i & (1<<j))
				V.eb(i, N+j);
	for(int i = 0; i < 10; i++) V.eb(N+i, N+10);
	for(int i = 0; i < N+10; i++) V.eb(i, N+11);
	for(int i = 0; i < 9; i++) V.eb(N+i, N+i+1);
 
	InitG(N+12, V.size());
	for(int i = 0; i < V.size(); i++)
		MakeG(i, V[i].first, V[i].second);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
#define sz(V) ((int)(V).size())
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
using namespace std;
typedef pair<int, int> pii;
static void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }
 
static const int MAXN = 1055;
 
static vector<int> G[MAXN], CG[MAXN];
static vector<int> VC;
 
static vector<pii> EV;
 
static int D[MAXN];
static bitset<MAXN> isVC;
 
static int N, A, B;
 
void Bob( int V, int U, int C[], int D[] ){
	::N = V-12;
 
	for(int i = 0; i < U; i++) fg(G, C[i], D[i]);
	for(int i = 0; i < V; i++) if(sz(G[i]) == V-2) A = i;
 
	{
		bitset<MAXN> chk;
		for(int v : G[A]) chk[v] = true;
		chk[A] = true;
 
		for(int i = 0; i < V; i++) if(!chk[i]) B = i;
	}
 
	VC = G[B];
	for(int v : VC) isVC[v] = true;
	for(int i = 0; i < U; i++)
		if(isVC[C[i]] && isVC[D[i]])
			fg(CG, C[i], D[i]);
 
	{
		int a = -1, b = -1;
		for(int v : VC) {
			if(1 < sz(CG[v])) continue;
			(a < 0 ? a : b) = v;
		}
 
		if(sz(G[a]) < sz(G[b])) swap(a, b);
 
		vector<int> V; V.eb(a);
		for(int i = CG[a][0]; i != b;) {
			int ta = CG[i][0], tb = CG[i][1];
			ta = ta + tb - V.back();
			V.eb(i);
			i = ta;
		}
		V.eb(b);
 
		VC = V;
	}
 
	for(int i = 0; i < 10; i++)
		for(int v : G[VC[i]])
			::D[v] |= 1<<i;
	::D[A] = ::D[B] = -1;
	for(int v : VC) ::D[v] = -1;
	
	for(int i = 0; i < V; i++) {
		for(int v : G[i]) {
			if(::D[i] < 0 || ::D[v] < 0) continue;
			if(::D[i] < ::D[v]) EV.eb(::D[i], ::D[v]);
		}
	}
 
	InitMap(N, sz(EV));
	for(pii v : EV) MakeMap(v.first, v.second);
}

Compilation message (stderr)

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

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