Submission #313392

#	Time	Username	Problem	Language	Result	Execution time	Memory
313392		Lawliet	Airline Route Map (JOI18_airline)	C++17	100 / 100	879 ms	31512 KiB

Alice

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

const int MAXN = 1010;
const int MAXM = 1000010;

using namespace std;
typedef pair<int,int> pii;

vector<pii> ans;

void Alice(int N, int M, int A[], int B[])
{
	if( N == 1 ) return void( InitG( 1 , 0 ) );

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

	for(int i = 1 ; i <= N ; i++)
		for(int j = 0 ; j < 10 ; j++)
			if( i & (1 << j) ) ans.push_back( { i - 1 , j + N } );//Representação binária

	for(int i = N ; i < N + 9 ; i++)
		ans.push_back( { i , i + 1 } );//Linha de bits

	for(int i = 0 ; i < N ; i++)
		ans.push_back( { i , N + 10 } );//A

	ans.push_back( { N + 10 , N + 11 } );//Folha

	InitG( N + 12 , (int)ans.size() );

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

Bob

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

using namespace std;
typedef pair<int,int> pii;

const int MAXN = 2000;

int perm[MAXN];
int value[MAXN];

bool mark[MAXN];
bool isOriginal[MAXN];

vector<int> bits;
vector<int> adj[MAXN];

bool cmp(int i, int j) { return adj[i].size() > adj[j].size(); }

void DFS(int cur)
{
	mark[cur] = true;

	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
		if( !mark[ adj[cur][i] ] ) DFS( adj[cur][i] );

	bits.push_back( cur );
}

void Bob(int V, int U, int C[], int D[])
{
	if( V == 1 ) return void( InitMap( 1 , 0 ) );

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

	int leaf = -1;

	for(int i = 0 ; i < V ; i++)
	{
		if( (int)adj[i].size() > 1 ) continue;

		if( leaf == -1 )
		{
			leaf = i;
			continue;
		}

		int vizI = adj[i].back();
		int vizLeaf = adj[leaf].back();

		if( (int)adj[vizLeaf].size() < (int)adj[vizI].size() )
			leaf = i;
	}

	int A = adj[leaf].back();
	mark[A] = true;

	for(int i = 0 ; i < (int)adj[A].size() ; i++)
	{
		mark[ adj[A][i] ] = true;
		isOriginal[ adj[A][i] ] = ( adj[A][i] != leaf );
	}

	int last = -1;

	for(int i = 0 ; i < V ; i++)
	{
		if( mark[i] ) continue;

		if( last == -1 ) last = i;
		else if( adj[i].size() < adj[last].size() ) last = i;
	}

	DFS( last );

	for(int i = 0 ; i < (int)bits.size() ; i++)
		mark[ bits[i] ] = false;

	for(int i = 0 ; i < (int)bits.size() ; i++)
		value[ bits[i] ] = (1 << i);

	for(int i = 0 ; i < V ; i++)
	{
		if( !mark[i] || i == A || i == leaf ) continue;

		for(int j = 0 ; j < (int)adj[i].size() ; j++)
			if( !mark[ adj[i][j] ] ) perm[i] += value[ adj[i][j] ];

		perm[i]--;
	}

	vector<pii> edges;

	for(int i = 0 ; i < U ; i++)
		if( isOriginal[ C[i] ] && isOriginal[ D[i] ] )
			edges.push_back( { perm[ C[i] ] , perm[ D[i] ] } );

	InitMap( V - 12 , (int)edges.size() );

	for(int i = 0 ; i < (int)edges.size() ; i++)
		MakeMap( edges[i].first , edges[i].second );
}

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