Submission #828857

#	Time	Username	Problem	Language	Result	Execution time	Memory
828857		MohamedAhmed04	Airline Route Map (JOI18_airline)	C++14	100 / 100	533 ms	29348 KiB

Alice

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

using namespace std ;

void Alice(int n, int m, int a[], int b[] )
{
	vector< pair<int , int> >vp ;
	for(int i = 0 ; i < m ; ++i)
		vp.emplace_back(a[i] , b[i]) ;
	for(int bit = 0 ; bit < 10 ; ++bit)
	{
		for(int i = 0 ; i < n ; ++i)
		{
			if((i & (1 << bit)))
				vp.emplace_back(i , n+bit) ;
		}
		if(bit+1 < 10)
			vp.emplace_back(n+bit , n+bit+1) ;
	}
	for(int i = 0 ; i < n+10 ; ++i)
		vp.emplace_back(i , n+10) ;
	for(int i = 0 ; i < 10 ; ++i)
		vp.emplace_back(n+i , n+11) ;
	InitG(n+12 , vp.size()) ;
	int idx = 0 ;
	for(auto &p : vp)
		MakeG(idx , p.first , p.second) , ++idx ;
}

Bob

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

using namespace std ;

const int MAX = 2004 ;

int deg[MAX] , taken[MAX] , mark[MAX] ;
int val[MAX] ;

vector< vector<int> >adj(MAX) ;

void Bob( int V, int U, int C[], int D[] )
{
	int n = V-12 ;
	if(n == 1)
	{
		InitMap(n , 0) ;
		return ;
	}
	for(int i = 0 ; i < U ; ++i)
	{
		adj[C[i]].push_back(D[i]) ;
		adj[D[i]].push_back(C[i]) ;
		deg[C[i]]++ , deg[D[i]]++ ;
	}
	int last = -1 ;
	for(int i = 0 ; i < V ; ++i)
	{
		if(deg[i] == n+10)
			last = i ;
	}
	for(auto &node : adj[last])
		taken[node] = 1 ;
	int now ;
	for(int i = 0 ; i < V ; ++i)
	{
		if((!taken[i]) && i != last)
		{
			now = i ;
			break ;
		}
	}
	assert(deg[now] == 10) ;
	for(auto &node : adj[now])
		mark[node] = 1 ;
	int Min = 1e9 , cur ;
	for(int i = 0 ; i < V ; ++i)
	{
		if(!mark[i])
			continue ;
		int cnt = 0 ;
		for(auto &child : adj[i])
			cnt += mark[child] ;
		if(cnt < Min)
			Min = cnt , cur = i ;
		else if(cnt == Min && deg[i] > deg[cur])
			cur = i ;
	}
	for(int i = 0 ; i < 10 ; ++i)
	{
		mark[cur] = 2 ;
		int nxt = -1 ;
		for(auto &node : adj[cur])
		{
			val[node] |= (1 << i) ;
			if(mark[node] == 1)
				nxt = node ;
		}
		cur = nxt ;
	}
	mark[now] = mark[last] = 1 ;
	vector< pair<int , int> >ans ;
	for(int i = 0 ; i < U ; ++i)
	{
		int x = C[i] , y = D[i] ;
		if((!mark[x]) && (!mark[y]))
			ans.emplace_back(val[x] , val[y]) ;
	}
	InitMap(n , ans.size()) ;
	for(auto &p : ans)
		MakeMap(p.first , p.second) ;
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:64:27: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |   for(auto &node : adj[cur])
      |                           ^
Bob.cpp:44:16: warning: 'now' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |  assert(deg[now] == 10) ;
      |                ^

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