Submission #1091271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091271		DobromirAngelov	Airline Route Map (JOI18_airline)	C++14	100 / 100	446 ms	36552 KiB

Alice

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

using namespace std;

static const int MAXN=1505;
static const int BIT_CNT=10;

static int n,m;
static vector<pair<int,int> > edges;
static int code[MAXN];
static int deg1=0;

void addEdge(int u,int v)
{
	if(u==n+1 || v==n+1) deg1++;
	edges.push_back({u-1,v-1});
}

void returnGraph()
{
	InitG(n+BIT_CNT+2, edges.size());
	int pos=0;
	for(auto cur: edges)
	{
		MakeG(pos++, cur.first, cur.second);
	}
}

void Alice( int N, int M, int A[], int B[] )
{
	n=N;
	m=M;
	for(int i=0;i<m;i++)
	{
		int u=A[i]+1;
		int v=B[i]+1;
		addEdge(u,v);
	}

	int ptr=1;
	for(int i=1;i<=n;i++)
	{
		while(__builtin_popcount(ptr)==9) ptr++;
		code[i]=ptr++;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<BIT_CNT;j++)
		{
			if(code[i]&(1<<j)) addEdge(i,n+1+j);
		}
	}

	for(int i=1;i<=n+BIT_CNT;i++)
	{
		if(i==n+1) continue;
		addEdge(n+BIT_CNT+1,i);
	}
	for(int i=1;i<=BIT_CNT;i++)
	{
		addEdge(n+BIT_CNT+2,n+i);
	}

	for(int i=2;i<BIT_CNT;i++)
	{
		addEdge(n+i-1,n+i);
	}
	if(deg1==BIT_CNT) addEdge(n+1,n+BIT_CNT);
	else addEdge(n+BIT_CNT-1,n+BIT_CNT);

	returnGraph();
}

Bob

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

using namespace std;

static const int MAXN=1505;
static const int BIT_CNT=10;

static int n,m;
static vector<int> adj[MAXN];
static int mark[MAXN];
static bool isBit[MAXN];
static int val[MAXN];
static int id[MAXN];
static int decode[MAXN];
static bool edge[MAXN][MAXN];
static vector<pair<int,int> > MapEdges;

void addMapEdge(int u,int v)
{
	MapEdges.push_back({u-1,v-1});
}

void returnMap()
{
	InitMap(n,MapEdges.size());
	for(auto cur: MapEdges)
	{
		MakeMap(cur.first, cur.second);
	}
}

void dfsBit(int v,int d,int par)
{
	int cnt=0;
	for(auto u: adj[v])
	{
		if(!isBit[u]) continue;
		if(u==par) continue;
		cnt++;
		dfsBit(u,d+1,v);
	}
	if(cnt==0 && d==1) val[v]=(1<<(BIT_CNT-1));
	else val[v]=(1<<d);
}

void Bob( int V, int U, int C[], int D[] )
{
	n=V-BIT_CNT-2;
	m=U;
	for(int i=0;i<m;i++)
	{
		int u=C[i]+1;
		int v=D[i]+1;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	int bigR=0;
	for(int i=1;i<=V;i++)
	{
		if(adj[i].size()==n+BIT_CNT-1)
		{
			bigR=i;
			break;
		}
	}
	for(auto u: adj[bigR])
	{
		mark[u]=1;
	}
	int smR=0;
	int bit1=0;
	for(int i=1;i<=V;i++)
	{
		if(i!=bigR && !mark[i])
		{
			if(adj[i].size()==BIT_CNT) smR=i;
			else bit1=i;
		}
	}

	for(auto u: adj[smR])
	{
		isBit[u]=1;
	}
	dfsBit(bit1, 0, -1);

	for(int i=1;i<=V;i++)
	{
		if(i==bigR || i==smR || isBit[i]) continue;
		for(auto u: adj[i])
		{
			if(isBit[u]) id[i]+=val[u];
		}
	}
	int ptr=1;
	for(int i=1;i<=n;i++)
	{
		while(__builtin_popcount(ptr)==9) ptr++;
		decode[ptr++]=i;
	}
	for(int i=1;i<=V;i++)
	{
		if(id[i]>0) id[i]=decode[id[i]];
	}

	for(int i=1;i<=V;i++)
	{
		if(i==bigR || i==smR || isBit[i]) continue;
		for(auto u: adj[i])
		{
			if(u==bigR || u==smR || isBit[u]) continue;
			edge[id[i]][id[u]]=1;
		}
	}
	for(int i=1;i<=V;i++)
	{
		for(int j=i+1;j<=V;j++)
		{
			if(edge[i][j]) addMapEdge(i,j);
		}
	}

	returnMap();
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:62:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |   if(adj[i].size()==n+BIT_CNT-1)
      |      ~~~~~~~~~~~~~^~~~~~~~~~~~~

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