oj.uz

Submission #313426

# Submission time Handle Problem Language Result Execution time Memory
313426 2020-10-16T00:42:38 Z CaroLinda Airline Route Map (JOI18_airline) C++14
37 / 100
 756 ms 30648 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[] ){

	if(N == 1)
	{
		InitG(1,0) ;
		return ;
	}

	int _log = 10 ;

	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) ) ;
	for(int i = 0 ; i < N+_log ; i++ ) edge.push_back( make_pair(N+_log+2 , i  ) ) ;

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

	InitG(N+_log+3, 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[] ){

	if(V == 1)
	{
		InitMap(1,0) ;
		return ;
	}

	int cnt = 0 ;

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

	vector<bool> mark(V, false) ;
	mark[ idx[V-1] ] = true ;

	for(auto e : adj[ idx[V-1] ])
		mark[e] = true ;

	int indicador ;
	for(int i = V-1 ; i >= 0 ; i-- )
		if( !mark[ idx[i] ] )
		{
			indicador = idx[i] ;
			mark[idx[i]] = true ;
			break ;
		}

	vector<bool> isBoring(V, false) ;
	vector<int> soma(V, 0) ;
	
	for(auto e : adj[indicador]) isBoring[e] = true , cnt++ ;

	//for(int i = 0 ; i < V ; i++ ) cout << idx[i] << " " << deg[idx[i]] << " " << isBoring[idx[i]] << endl ;

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

	for(int i = 0 ; i < V ; i++ ) mark[i] = false ;
	mark[ idx[V-1] ] = true ;
	
	int curBit = V - cnt - 2 - 1 ;
	while(curLast != -1)
	{

		mark[curLast] = true ;

		int nxt = -1 ;

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

		curBit--;
		curLast = 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 ) ) ;

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

	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:71:15: warning: 'curLast' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |   mark[curLast] = true ;
      |               ^
Bob.cpp:56:28: warning: 'indicador' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |  for(auto e : adj[indicador]) isBoring[e] = true , cnt++ ;
      |                            ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6912 KB Output is correct
2 Correct 7 ms 6912 KB Output is correct
3 Correct 7 ms 6912 KB Output is correct
4 Correct 7 ms 6912 KB Output is correct
5 Correct 6 ms 6912 KB Output is correct
6 Correct 6 ms 6912 KB Output is correct
7 Correct 6 ms 6912 KB Output is correct
8 Correct 6 ms 6912 KB Output is correct
9 Correct 6 ms 6912 KB Output is correct
10 Correct 6 ms 6656 KB Output is correct
11 Correct 6 ms 6912 KB Output is correct
12 Correct 6 ms 6912 KB Output is correct
13 Correct 6 ms 6912 KB Output is correct
14 Correct 6 ms 6912 KB Output is correct
15 Correct 6 ms 6912 KB Output is correct
16 Correct 6 ms 6912 KB Output is correct
17 Correct 6 ms 6912 KB Output is correct
18 Correct 6 ms 6912 KB Output is correct
19 Correct 7 ms 6912 KB Output is correct
20 Correct 7 ms 6912 KB Output is correct
21 Correct 6 ms 6912 KB Output is correct
22 Correct 6 ms 6912 KB Output is correct
23 Correct 6 ms 6912 KB Output is correct
24 Correct 6 ms 6912 KB Output is correct
25 Correct 6 ms 6912 KB Output is correct
26 Correct 6 ms 6912 KB Output is correct
27 Correct 6 ms 6912 KB Output is correct
28 Correct 6 ms 6912 KB Output is correct
29 Correct 6 ms 6912 KB Output is correct
30 Correct 6 ms 6656 KB Output is correct
31 Correct 7 ms 7168 KB Output is correct
32 Correct 6 ms 6912 KB Output is correct
33 Correct 6 ms 6656 KB Output is correct
34 Correct 6 ms 6656 KB Output is correct
35 Correct 6 ms 6912 KB Output is correct
36 Correct 6 ms 6912 KB Output is correct
37 Correct 6 ms 7168 KB Output is correct
38 Correct 6 ms 6912 KB Output is correct
39 Correct 6 ms 6912 KB Output is correct
40 Correct 6 ms 6912 KB Output is correct
41 Correct 7 ms 6912 KB Output is correct
42 Correct 6 ms 6912 KB Output is correct
43 Correct 6 ms 6912 KB Output is correct
44 Correct 6 ms 6656 KB Output is correct
45 Correct 7 ms 6656 KB Output is correct
46 Correct 6 ms 6912 KB Output is correct
47 Correct 6 ms 6912 KB Output is correct
48 Correct 6 ms 6912 KB Output is correct
49 Correct 7 ms 6912 KB Output is correct
50 Correct 6 ms 6656 KB Output is correct
51 Correct 6 ms 6656 KB Output is correct
52 Correct 6 ms 6912 KB Output is correct
53 Correct 6 ms 6656 KB Output is correct
54 Correct 7 ms 6912 KB Output is correct
55 Correct 6 ms 6912 KB Output is correct
56 Correct 6 ms 6912 KB Output is correct
57 Correct 6 ms 6912 KB Output is correct
58 Correct 6 ms 6912 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6912 KB Output is correct
2 Correct 7 ms 6912 KB Output is correct
3 Correct 7 ms 6912 KB Output is correct
4 Correct 7 ms 6912 KB Output is correct
5 Correct 6 ms 6912 KB Output is correct
6 Correct 6 ms 6912 KB Output is correct
7 Correct 6 ms 6912 KB Output is correct
8 Correct 6 ms 6912 KB Output is correct
9 Correct 6 ms 6912 KB Output is correct
10 Correct 6 ms 6656 KB Output is correct
11 Correct 6 ms 6912 KB Output is correct
12 Correct 6 ms 6912 KB Output is correct
13 Correct 6 ms 6912 KB Output is correct
14 Correct 6 ms 6912 KB Output is correct
15 Correct 6 ms 6912 KB Output is correct
16 Correct 6 ms 6912 KB Output is correct
17 Correct 6 ms 6912 KB Output is correct
18 Correct 6 ms 6912 KB Output is correct
19 Correct 7 ms 6912 KB Output is correct
20 Correct 7 ms 6912 KB Output is correct
21 Correct 6 ms 6912 KB Output is correct
22 Correct 6 ms 6912 KB Output is correct
23 Correct 6 ms 6912 KB Output is correct
24 Correct 6 ms 6912 KB Output is correct
25 Correct 6 ms 6912 KB Output is correct
26 Correct 6 ms 6912 KB Output is correct
27 Correct 6 ms 6912 KB Output is correct
28 Correct 6 ms 6912 KB Output is correct
29 Correct 6 ms 6912 KB Output is correct
30 Correct 6 ms 6656 KB Output is correct
31 Correct 7 ms 7168 KB Output is correct
32 Correct 6 ms 6912 KB Output is correct
33 Correct 6 ms 6656 KB Output is correct
34 Correct 6 ms 6656 KB Output is correct
35 Correct 6 ms 6912 KB Output is correct
36 Correct 6 ms 6912 KB Output is correct
37 Correct 6 ms 7168 KB Output is correct
38 Correct 6 ms 6912 KB Output is correct
39 Correct 6 ms 6912 KB Output is correct
40 Correct 6 ms 6912 KB Output is correct
41 Correct 7 ms 6912 KB Output is correct
42 Correct 6 ms 6912 KB Output is correct
43 Correct 6 ms 6912 KB Output is correct
44 Correct 6 ms 6656 KB Output is correct
45 Correct 7 ms 6656 KB Output is correct
46 Correct 6 ms 6912 KB Output is correct
47 Correct 6 ms 6912 KB Output is correct
48 Correct 6 ms 6912 KB Output is correct
49 Correct 7 ms 6912 KB Output is correct
50 Correct 6 ms 6656 KB Output is correct
51 Correct 6 ms 6656 KB Output is correct
52 Correct 6 ms 6912 KB Output is correct
53 Correct 6 ms 6656 KB Output is correct
54 Correct 7 ms 6912 KB Output is correct
55 Correct 6 ms 6912 KB Output is correct
56 Correct 6 ms 6912 KB Output is correct
57 Correct 6 ms 6912 KB Output is correct
58 Correct 6 ms 6912 KB Output is correct
59 Correct 7 ms 6912 KB Output is correct
60 Correct 7 ms 6912 KB Output is correct
61 Correct 7 ms 6912 KB Output is correct
62 Correct 6 ms 6912 KB Output is correct
63 Correct 6 ms 6912 KB Output is correct
64 Correct 7 ms 6912 KB Output is correct
65 Correct 8 ms 6912 KB Output is correct
66 Correct 7 ms 6912 KB Output is correct
67 Correct 7 ms 6912 KB Output is correct
68 Correct 7 ms 6912 KB Output is correct
69 Correct 6 ms 6912 KB Output is correct
70 Correct 6 ms 6912 KB Output is correct
71 Correct 7 ms 6912 KB Output is correct
72 Correct 7 ms 6912 KB Output is correct
73 Correct 7 ms 6912 KB Output is correct
74 Correct 7 ms 6912 KB Output is correct
75 Correct 6 ms 6912 KB Output is correct
76 Correct 7 ms 6912 KB Output is correct
77 Correct 6 ms 6912 KB Output is correct
78 Correct 7 ms 6912 KB Output is correct
79 Correct 7 ms 6912 KB Output is correct
80 Correct 7 ms 6912 KB Output is correct
81 Correct 6 ms 6912 KB Output is correct
82 Correct 6 ms 6912 KB Output is correct
83 Correct 6 ms 6912 KB Output is correct
84 Correct 6 ms 6912 KB Output is correct
85 Correct 7 ms 6912 KB Output is correct
86 Correct 7 ms 6912 KB Output is correct
87 Correct 6 ms 6912 KB Output is correct
88 Correct 6 ms 6912 KB Output is correct
89 Correct 6 ms 6912 KB Output is correct
90 Correct 6 ms 6656 KB Output is correct
91 Correct 6 ms 6912 KB Output is correct
92 Correct 6 ms 6912 KB Output is correct
93 Correct 6 ms 6656 KB Output is correct
94 Correct 7 ms 6912 KB Output is correct
95 Correct 7 ms 6912 KB Output is correct
96 Correct 7 ms 6912 KB Output is correct
97 Correct 7 ms 6912 KB Output is correct
98 Correct 7 ms 6912 KB Output is correct
99 Correct 6 ms 6912 KB Output is correct
100 Correct 6 ms 6912 KB Output is correct
101 Correct 6 ms 6912 KB Output is correct
102 Correct 7 ms 6912 KB Output is correct
103 Correct 6 ms 6912 KB Output is correct
104 Correct 6 ms 6912 KB Output is correct
105 Correct 8 ms 7168 KB Output is correct
106 Correct 7 ms 6912 KB Output is correct
107 Correct 7 ms 6976 KB Output is correct
108 Correct 6 ms 6912 KB Output is correct
109 Correct 7 ms 6912 KB Output is correct
110 Correct 7 ms 6912 KB Output is correct
111 Correct 7 ms 7168 KB Output is correct
112 Correct 7 ms 6912 KB Output is correct
113 Correct 6 ms 6912 KB Output is correct
114 Correct 6 ms 6912 KB Output is correct
115 Correct 8 ms 6912 KB Output is correct
116 Correct 6 ms 6912 KB Output is correct
117 Correct 6 ms 6912 KB Output is correct
118 Correct 6 ms 6912 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 756 ms 30648 KB Wrong Answer [10]
2 Halted 0 ms 0 KB -