oj.uz

Submission #828841

# Submission time Handle Problem Language Result Execution time Memory
828841 2023-08-17T17:19:05 Z MohamedAhmed04 Airline Route Map (JOI18_airline) C++14
0 / 100
 417 ms 29156 KB 
#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) ;
		}
	}
	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) ;
	for(int i = 0 ; i < 10 ; ++i)
	{
		for(int j = i+1 ; j < 10 ; ++j)
			vp.emplace_back(n+i , n+j) ;
	}
	InitG(n+12 , vp.size()) ;
	int idx = 0 ;
	for(auto &p : vp)
		MakeG(idx , p.first , p.second) , ++idx ;
}


#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 ;
	vector< pair<int , int> >bits ;
	for(int i = 0 ; i < V ; ++i)
	{
		if(mark[i])
			bits.emplace_back(deg[i] , i) ;
	}
	sort(bits.begin() , bits.end()) ;
	reverse(bits.begin() , bits.end()) ;
	for(int i = 0 ; i < 10 ; ++i)
	{
		for(auto &node : adj[bits[i].second])
			val[node] |= (1 << i) ;
	}
	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

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

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4740 KB Output is correct
2 Failed 2 ms 4664 KB Wrong Answer [13]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4740 KB Output is correct
2 Failed 2 ms 4664 KB Wrong Answer [13]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 29156 KB Output is correct : V - N = 12
2 Failed 388 ms 25640 KB Wrong Answer [13]
3 Halted 0 ms 0 KB -