oj.uz

Submission #313420

# Submission time Handle Problem Language Result Execution time Memory
313420 2020-10-16T00:21:40 Z CaroLinda Airline Route Map (JOI18_airline) C++14
0 / 100
 737 ms 30760 KB 
#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 = 0 ; j < N ; j++ )
			if(isOn(i,j+1)) edge.push_back( make_pair(i+N, j) ) ;

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

	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 ) ) ;

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

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

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

}


#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] && i != idx[V-1]) isBoring[i] = true ;

	//for(int i = 0 ; i < V ; i++ ) cout << idx[i] << " " << deg[idx[i]] << " " << isBoring[i] << endl ;
	vector<bool> mark(V, false) ;
	mark[ idx[V-1] ] = mark[idx[0]]=true ;

	int prim ;
	for(int i : adj[ idx[V-1] ] )
		mark[i] = true ;

	for(int i = 0 ; i < V ; i++ )
		if(!mark[i]) prim = i ;

	for(int i = 0 ; i < V ; i++ ) mark[i] = false ;

	mark[ idx[V-1] ] = true ;

	int curBit = 0 ;
	while(prim != -1)
	{
		int nxt = -1 ;

		mark[prim] = true ;

		for(auto e : adj[prim])
		{
			if(isBoring[e] )
				soma[e] += (1<<curBit) ;
			else if(!mark[e] ) nxt = e ;
		}

		curBit++ ;	
		prim = nxt ;
	}

	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 ) ;

}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:58:12: warning: 'prim' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |   mark[prim] = true ;
      |            ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6912 KB Output is correct
2 Correct 6 ms 6912 KB Output is correct
3 Correct 6 ms 6912 KB Output is correct
4 Correct 6 ms 6912 KB Output is correct
5 Correct 6 ms 6912 KB Output is correct
6 Correct 7 ms 6912 KB Output is correct
7 Incorrect 6 ms 6912 KB Wrong Answer [120]
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6912 KB Output is correct
2 Correct 6 ms 6912 KB Output is correct
3 Correct 6 ms 6912 KB Output is correct
4 Correct 6 ms 6912 KB Output is correct
5 Correct 6 ms 6912 KB Output is correct
6 Correct 7 ms 6912 KB Output is correct
7 Incorrect 6 ms 6912 KB Wrong Answer [120]
8 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Partially correct 669 ms 30760 KB Output is partially correct : V - N = 13
2 Partially correct 516 ms 26152 KB Output is partially correct : V - N = 13
3 Partially correct 200 ms 14048 KB Output is partially correct : V - N = 13
4 Partially correct 15 ms 7424 KB Output is partially correct : V - N = 13
5 Partially correct 125 ms 11224 KB Output is partially correct : V - N = 13
6 Partially correct 449 ms 24000 KB Output is partially correct : V - N = 13
7 Partially correct 670 ms 30152 KB Output is partially correct : V - N = 13
8 Partially correct 737 ms 27848 KB Output is partially correct : V - N = 13
9 Partially correct 319 ms 17616 KB Output is partially correct : V - N = 13
10 Partially correct 55 ms 8424 KB Output is partially correct : V - N = 13
11 Partially correct 92 ms 9184 KB Output is partially correct : V - N = 13
12 Partially correct 352 ms 19152 KB Output is partially correct : V - N = 13
13 Partially correct 627 ms 28872 KB Output is partially correct : V - N = 13
14 Partially correct 663 ms 29856 KB Output is partially correct : V - N = 13
15 Partially correct 550 ms 22748 KB Output is partially correct : V - N = 13
16 Partially correct 86 ms 10200 KB Output is partially correct : V - N = 13
17 Partially correct 26 ms 7680 KB Output is partially correct : V - N = 13
18 Partially correct 250 ms 15824 KB Output is partially correct : V - N = 13
19 Partially correct 574 ms 26840 KB Output is partially correct : V - N = 13
20 Partially correct 728 ms 30664 KB Output is partially correct : V - N = 13
21 Correct 189 ms 13272 KB Output is correct : V - N = 12
22 Correct 149 ms 11992 KB Output is correct : V - N = 12
23 Partially correct 64 ms 8928 KB Output is partially correct : V - N = 13
24 Partially correct 9 ms 6912 KB Output is partially correct : V - N = 13
25 Partially correct 39 ms 8184 KB Output is partially correct : V - N = 13
26 Correct 160 ms 10968 KB Output is correct : V - N = 12
27 Partially correct 228 ms 13560 KB Output is partially correct : V - N = 13
28 Partially correct 164 ms 12504 KB Output is partially correct : V - N = 13
29 Partially correct 84 ms 9696 KB Output is partially correct : V - N = 13
30 Partially correct 13 ms 7528 KB Output is partially correct : V - N = 13
31 Partially correct 13 ms 7168 KB Output is partially correct : V - N = 13
32 Partially correct 12 ms 7168 KB Output is partially correct : V - N = 13
33 Partially correct 12 ms 7168 KB Output is partially correct : V - N = 13
34 Partially correct 13 ms 7168 KB Output is partially correct : V - N = 13
35 Partially correct 12 ms 7168 KB Output is partially correct : V - N = 13
36 Incorrect 708 ms 30664 KB Wrong Answer [12]
37 Halted 0 ms 0 KB -