Submission #56744

#	Time	Username	Problem	Language	Result	Execution time	Memory
56744		Diuven	Airline Route Map (JOI18_airline)	C++11	100 / 100	748 ms	31040 KiB

Alice

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

using namespace std;

typedef pair<int, int> pii;

int n_A, m_A;

vector<pii> E;

void Alice( int N, int M, int A[], int B[] ){
	n_A=N, m_A=M;
	for(int i=0; i<m_A; i++){
		E.push_back({A[i], B[i]});
	}

	int P=N, Q=N+1;

	int X[10];
	for(int i=0; i<10; i++) X[i]=N+i+2;

	for(int i=0; i<N; i++){
		for(int j=0; j<10; j++)
			if(i&(1<<j))
				E.push_back({i, X[j]});
	}

	for(int i=0; i<10; i++)
		E.push_back({X[i], P});
	
	for(int i=0; i<N; i++)
		E.push_back({i, P});
	
	for(int i=0; i<10; i++)
		E.push_back({X[i], Q});

	for(int i=0; i<9; i++)
		E.push_back({X[i], X[i+1]});

	InitG(N+12, E.size());

	for(int i=0; i<(int)E.size(); i++){
		MakeG(i, E[i].first, E[i].second);
	}

}

Bob

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

typedef pair<int, int> pii;

const int MX=2020;

int n_B, m_B;

bool G[MX][MX];
int deg1[MX];
vector<pii> ans;

void Bob( int V, int U, int C[], int D[] ){
	n_B=V, m_B=U;
	for(int i=0; i<m_B; i++){
		G[C[i]][D[i]]=G[D[i]][C[i]]=true;
		deg1[C[i]]++, deg1[D[i]]++;
	}

	int P=-1, Q=-1, N=V-12;

	for(int i=0; i<V; i++)
		if(deg1[i]==N+10) P=i;
	
	for(int i=0; i<V; i++)
		if(i!=P && !G[i][P]) Q=i;

	vector<int> X, Y;
	int deg2[10]={};
	bool done[MX]={};

	for(int i=0; i<V; i++)
		if(G[i][Q]) X.push_back(i);

	for(int i=0; i<10; i++)
		for(int j=i+1; j<10; j++)
			if(G[X[i]][X[j]]){
				deg1[X[i]]--, deg1[X[j]]--;
				deg2[i]++, deg2[j]++;
			}

	
	int a=-1, b=-1;
	for(int i=0; i<10; i++){
		if(deg2[i]==2) continue;
		if(a<0) a=X[i];
		else b=X[i];
	}

	if(deg1[a]<deg1[b]) swap(a, b);
	
	int now=a;

	Y.push_back(a);
	for(int i=0, now=a; i<10; i++){
		done[now]=true;
		for(int j=0; j<10; j++){
			if(!done[X[j]] && G[now][X[j]]){
				now=X[j]; break;
			}
		}
		Y.push_back(now);
	}

	int rev[MX]={};
	bool out[MX]={};

	for(int i=0; i<10; i++) out[Y[i]]=true;
	out[P]=out[Q]=true;

	for(int i=0; i<V; i++){
		if(out[i]) continue;
		for(int j=0; j<10; j++)
			rev[i]+=(G[i][Y[j]] ? (1<<j) : 0);
	}

	for(int i=0; i<V; i++){
		for(int j=i+1; j<V; j++){
			if(out[i] || out[j]) continue;
			if(!G[i][j]) continue;
			int x=rev[i], y=rev[j];
			ans.push_back({x,y});
		}
	}

	InitMap(N, ans.size());

	for(pii &p:ans)
		MakeMap(p.first, p.second);
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:56:6: warning: unused variable 'now' [-Wunused-variable]
  int now=a;
      ^~~

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