Submission #313391

#	Time	Username	Problem	Language	Result	Execution time	Memory
313391		CaroLinda	Airline Route Map (JOI18_airline)	C++14	0 / 100	688 ms	30664 KiB

Alice

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

#define sz(x) (int)(x.size())

using namespace std ;

bool isOn(int i, int m) { return ((1<<i)&m) != 0 ; }

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


	int _log ;

	for(_log = 0 ; _log < 13 ; _log++ )
		if( (1<<_log) > N+1 )
		{
			_log--;
			break ;
		}

	vector< pair<int,int> > edge ;

	for(int i = 0 ; i< M ; i++ ) edge.push_back( make_pair(A[i] , B[i]) ) ;

	for(int i = 0 ; i <= _log ; i++ )
		for(int j = i+1 ; j <= _log ; j++ )
			edge.push_back( make_pair(N+i, N+j) ) ;

	for(int i = 0 ; i <= _log ; i++ )
		for(int j = 0 ; j < N ; j++ )
			if(isOn(i,j+1)) edge.push_back( make_pair(i+N, j) ) ;

	for(int i = 0 ; i < N ; i++ ) edge.push_back( make_pair(N+_log+1, i) ) ;
	edge.push_back(make_pair(N+_log+1, N+_log+2 ) ) ;

	InitG(N+_log+3, sz(edge)) ;
	for(int i = 0 ; i < sz(edge) ; i++ ) MakeG( i, edge[i].first, edge[i].second ); 

}

Bob

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

#define debug printf
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())

using namespace std ;

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


	vector<int> deg( V, 0 ) ;
	vector<vector<int> > adj(V, vector<int>()) ;

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

		adj[ C[i] ].push_back(D[i]) ;
		adj[ D[i] ].push_back(C[i]) ;

	}

	vector<int> idx(V) ; iota(all(idx), 0) ;
	sort(all(idx) ,[&](int i, int j) { return deg[i] < deg[j]; }) ;

	int indicador = adj[ idx[0] ][0] ;

	vector<bool> isBoring(V, false) ;
	vector<int> soma(V, 0) ;

	for(int i : adj[indicador]) 
		if(i != idx[0]) isBoring[i] = true ;

	for(int i = sz(idx)-1 , bitAtual = 0; i > 0 ; i-- )
	{
		int cur = idx[i] ;
		
		if(cur == indicador || isBoring[cur] ) continue ;

		for(int j : adj[cur] ) 
			if(isBoring[j])
				soma[j] += (1<<bitAtual) ;

		bitAtual++ ;

	}


	vector< pair<int,int> > edge ;

	for(int i = 0 ; i < U ; i++ )
	{
		int a = C[i] ;
		int b = D[i] ;

		if( !isBoring[a] || !isBoring[b] ) continue ;

		edge.push_back( make_pair( soma[a]-1, soma[b]-1 ) ) ;

	}

//	for(auto e : edge ) cout << e.first << " " << e.second << endl ;

	int cnt = 0 ;
	for(int i = 0 ; i < sz(isBoring) ; i++ ) cnt += isBoring[i] ;

	InitMap(cnt, sz(edge)) ;
	for(auto e : edge ) MakeMap(e.first, e.second ) ;

}

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