oj.uz

Submission #296734

# Submission time Handle Problem Language Result Execution time Memory
296734 2020-09-10T20:37:53 Z Plurm Airline Route Map (JOI18_airline) C++11
37 / 100
 664 ms 38824 KB 
#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

int vg[1024][1024]; // virtual graph
void Alice( int N, int M, int A[], int B[] ){
	for(int i = 0; i < M; i++){
		if(A[i] > B[i]) swap(A[i], B[i]);
		vg[A[i]][B[i]] = 1;
	}
	for(int i = 0; i < N; i++){
		vg[i][N] = 1;
		for(int b = 0; b < 10; b++){
			if(i & (1 << b)){
				vg[i][N+1+b] = 1;
			}
		}
	}
	for(int i = 0; i < 5; i++){
		for(int j = 0; j < i; j++){
			vg[N+1+i][N+6+j] = 1;
		}
		vg[N+1+i][N+11] = 1;
	}
	vg[0][N+11] = 1;
	if(N <= 40){
		for(int i = N+12; i <= 100; i++){
			vg[N][i] = 1;
		}
	}
	vector<pair<int,int> > ev;
	const int V = N <= 40 ? 100 : N+12;
	for(int i = 0; i < V; i++){
		for(int j = i+1; j < V; j++){
			if(vg[i][j]) ev.emplace_back(i,j);
		}
	}
	InitG(V, ev.size());
	for(int i = 0; i < ev.size(); i++){
		int x, y;
		tie(x, y) = ev[i];
		MakeG(i, x, y);
	}
}


#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

int bvg[1024][1024];
bool isOriginal[1024];
int p[1024];
void Bob( int V, int U, int C[], int D[] ){
	int N = 0;
	for(int i = 0; i < U; i++){
		bvg[C[i]][D[i]] = bvg[D[i]][C[i]] = 1;
	}
	for(int i = 0; i < V; i++){
		int chc = 0;
		for(int j = 0; j < V; j++) if(bvg[i][j]) chc++;
		if(chc == 1) continue;
	}
	int SIG = -1;
	int mx = -1;
	for(int i = 0; i < V; i++){
		isOriginal[i] = true;
		int cnt = 0;
		for(int j = 0; j < V; j++){
			cnt += bvg[i][j];
		}
		if(cnt > mx){
			SIG = i;
			mx = cnt;
		}
	}
	assert(SIG != -1);
	isOriginal[SIG] = false;
	vector<int> bits;
	for(int i = 0; i < V; i++){
		if(bvg[SIG][i] == 0 && i != SIG){
			bits.push_back(i);
			isOriginal[i] = false;
		}
	}
	int BSIG = -1;
	int ZERO = -1;
	for(int i : bits){
		int chco = 0;
		int chci = 0;
		for(int j = 0; j < V; j++) if(bvg[i][j]) chco++;
		for(int j : bits) if(bvg[i][j]) chci++;
		if(chco == 6 && chci == 5) BSIG = i;
	}
	for(int i = 0; i < V; i++){
		if(bvg[SIG][i] && bvg[i][BSIG]){
			ZERO = i;
		}
	}
	assert(BSIG != -1);
	assert(ZERO != -1);
	bvg[BSIG][ZERO] = bvg[ZERO][BSIG] = 0;
	bits.erase(find(bits.begin(), bits.end(), BSIG));
	isOriginal[ZERO] = true;
	vector<int> leftbits, rightbits;
	for(int i : bits){
		if(bvg[BSIG][i]) leftbits.push_back(i);
		else rightbits.push_back(i);
		bvg[BSIG][i] = bvg[i][BSIG] = 0;
		int chc = 0;
		for(int j : bits) if(bvg[i][j]) chc++;
	}
	sort(leftbits.begin(), leftbits.end(), [&bits](int b1, int b2){
		int chc1 = 0;
		int chc2 = 0;
		for(int i : bits) if(bvg[b1][i]) chc1++;
		for(int i : bits) if(bvg[b2][i]) chc2++;
		return chc1 < chc2;
	});
	sort(rightbits.begin(), rightbits.end(), [&bits](int b1, int b2){
		int chc1 = 0;
		int chc2 = 0;
		for(int i : bits) if(bvg[b1][i]) chc1++;
		for(int i : bits) if(bvg[b2][i]) chc2++;
		return chc1 > chc2;
	});
	bits = leftbits;
	for(int x : rightbits) bits.push_back(x);
	for(int i = 0; i < 10; i++){
		p[bits[i]] = N+1+i;
	}
	for(int i = 0; i < V; i++){
		if(isOriginal[i] && i != ZERO){
			int name = 0;
			for(int j = 0; j < 10; j++){
				if(bvg[i][bits[j]]) name += 1 << j;
			}
			p[i] = name;
			if(name == 0) isOriginal[i] = false;
			else N++;
		}else if(i == ZERO) N++;
	}
	vector<pair<int,int> > ev;
	for(int i = 0; i < U; i++){
		if(isOriginal[C[i]] && isOriginal[D[i]]){
			ev.emplace_back(p[C[i]], p[D[i]]);
		}
	}
	InitMap(N, ev.size());
	for(auto p : ev){
		MakeMap(p.first, p.second);
	}
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0; i < ev.size(); i++){
      |                 ~~^~~~~~~~~~~

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 6 ms 6912 KB Output is correct
5 Correct 7 ms 6912 KB Output is correct
6 Correct 7 ms 6912 KB Output is correct
7 Correct 7 ms 6912 KB Output is correct
8 Correct 6 ms 6912 KB Output is correct
9 Correct 7 ms 7168 KB Output is correct
10 Correct 8 ms 6912 KB Output is correct
11 Correct 6 ms 6912 KB Output is correct
12 Correct 7 ms 6912 KB Output is correct
13 Correct 7 ms 6912 KB Output is correct
14 Correct 6 ms 6912 KB Output is correct
15 Correct 7 ms 6912 KB Output is correct
16 Correct 7 ms 6912 KB Output is correct
17 Correct 6 ms 6912 KB Output is correct
18 Correct 7 ms 6912 KB Output is correct
19 Correct 7 ms 6912 KB Output is correct
20 Correct 6 ms 6912 KB Output is correct
21 Correct 7 ms 6912 KB Output is correct
22 Correct 7 ms 6912 KB Output is correct
23 Correct 7 ms 6912 KB Output is correct
24 Correct 7 ms 6912 KB Output is correct
25 Correct 7 ms 6976 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 7 ms 6912 KB Output is correct
31 Correct 6 ms 6912 KB Output is correct
32 Correct 7 ms 6912 KB Output is correct
33 Correct 6 ms 6912 KB Output is correct
34 Correct 7 ms 6912 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 6912 KB Output is correct
38 Correct 7 ms 6912 KB Output is correct
39 Correct 7 ms 6912 KB Output is correct
40 Correct 6 ms 6912 KB Output is correct
41 Correct 6 ms 6912 KB Output is correct
42 Correct 6 ms 6912 KB Output is correct
43 Correct 7 ms 6912 KB Output is correct
44 Correct 6 ms 6912 KB Output is correct
45 Correct 6 ms 6912 KB Output is correct
46 Correct 6 ms 6912 KB Output is correct
47 Correct 7 ms 6912 KB Output is correct
48 Correct 7 ms 6912 KB Output is correct
49 Correct 7 ms 7168 KB Output is correct
50 Correct 6 ms 6912 KB Output is correct
51 Correct 7 ms 6912 KB Output is correct
52 Correct 6 ms 6912 KB Output is correct
53 Correct 6 ms 6912 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 7 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 6 ms 6912 KB Output is correct
5 Correct 7 ms 6912 KB Output is correct
6 Correct 7 ms 6912 KB Output is correct
7 Correct 7 ms 6912 KB Output is correct
8 Correct 6 ms 6912 KB Output is correct
9 Correct 7 ms 7168 KB Output is correct
10 Correct 8 ms 6912 KB Output is correct
11 Correct 6 ms 6912 KB Output is correct
12 Correct 7 ms 6912 KB Output is correct
13 Correct 7 ms 6912 KB Output is correct
14 Correct 6 ms 6912 KB Output is correct
15 Correct 7 ms 6912 KB Output is correct
16 Correct 7 ms 6912 KB Output is correct
17 Correct 6 ms 6912 KB Output is correct
18 Correct 7 ms 6912 KB Output is correct
19 Correct 7 ms 6912 KB Output is correct
20 Correct 6 ms 6912 KB Output is correct
21 Correct 7 ms 6912 KB Output is correct
22 Correct 7 ms 6912 KB Output is correct
23 Correct 7 ms 6912 KB Output is correct
24 Correct 7 ms 6912 KB Output is correct
25 Correct 7 ms 6976 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 7 ms 6912 KB Output is correct
31 Correct 6 ms 6912 KB Output is correct
32 Correct 7 ms 6912 KB Output is correct
33 Correct 6 ms 6912 KB Output is correct
34 Correct 7 ms 6912 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 6912 KB Output is correct
38 Correct 7 ms 6912 KB Output is correct
39 Correct 7 ms 6912 KB Output is correct
40 Correct 6 ms 6912 KB Output is correct
41 Correct 6 ms 6912 KB Output is correct
42 Correct 6 ms 6912 KB Output is correct
43 Correct 7 ms 6912 KB Output is correct
44 Correct 6 ms 6912 KB Output is correct
45 Correct 6 ms 6912 KB Output is correct
46 Correct 6 ms 6912 KB Output is correct
47 Correct 7 ms 6912 KB Output is correct
48 Correct 7 ms 6912 KB Output is correct
49 Correct 7 ms 7168 KB Output is correct
50 Correct 6 ms 6912 KB Output is correct
51 Correct 7 ms 6912 KB Output is correct
52 Correct 6 ms 6912 KB Output is correct
53 Correct 6 ms 6912 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 7 ms 6912 KB Output is correct
59 Correct 7 ms 7168 KB Output is correct
60 Correct 7 ms 7424 KB Output is correct
61 Correct 7 ms 7168 KB Output is correct
62 Correct 7 ms 7168 KB Output is correct
63 Correct 6 ms 7168 KB Output is correct
64 Correct 7 ms 7168 KB Output is correct
65 Correct 7 ms 7168 KB Output is correct
66 Correct 7 ms 7168 KB Output is correct
67 Correct 7 ms 7168 KB Output is correct
68 Correct 6 ms 7168 KB Output is correct
69 Correct 7 ms 7168 KB Output is correct
70 Correct 7 ms 7168 KB Output is correct
71 Correct 7 ms 7168 KB Output is correct
72 Correct 7 ms 7168 KB Output is correct
73 Correct 8 ms 7168 KB Output is correct
74 Correct 6 ms 7168 KB Output is correct
75 Correct 6 ms 7168 KB Output is correct
76 Correct 7 ms 7168 KB Output is correct
77 Correct 7 ms 7168 KB Output is correct
78 Correct 7 ms 7168 KB Output is correct
79 Correct 7 ms 7168 KB Output is correct
80 Correct 7 ms 7232 KB Output is correct
81 Correct 6 ms 7168 KB Output is correct
82 Correct 6 ms 7168 KB Output is correct
83 Correct 6 ms 7168 KB Output is correct
84 Correct 6 ms 7168 KB Output is correct
85 Correct 7 ms 7168 KB Output is correct
86 Correct 6 ms 7168 KB Output is correct
87 Correct 7 ms 7168 KB Output is correct
88 Correct 6 ms 7168 KB Output is correct
89 Correct 7 ms 7168 KB Output is correct
90 Correct 7 ms 7168 KB Output is correct
91 Correct 6 ms 7168 KB Output is correct
92 Correct 6 ms 7168 KB Output is correct
93 Correct 6 ms 7168 KB Output is correct
94 Correct 7 ms 7168 KB Output is correct
95 Correct 7 ms 7168 KB Output is correct
96 Correct 7 ms 7168 KB Output is correct
97 Correct 7 ms 7168 KB Output is correct
98 Correct 7 ms 7168 KB Output is correct
99 Correct 6 ms 7168 KB Output is correct
100 Correct 6 ms 7168 KB Output is correct
101 Correct 6 ms 7168 KB Output is correct
102 Correct 6 ms 7168 KB Output is correct
103 Correct 7 ms 7168 KB Output is correct
104 Correct 6 ms 7168 KB Output is correct
105 Correct 8 ms 7168 KB Output is correct
106 Correct 7 ms 7168 KB Output is correct
107 Correct 6 ms 7168 KB Output is correct
108 Correct 6 ms 7168 KB Output is correct
109 Correct 7 ms 7168 KB Output is correct
110 Correct 7 ms 7168 KB Output is correct
111 Correct 7 ms 7168 KB Output is correct
112 Correct 7 ms 7168 KB Output is correct
113 Correct 6 ms 7168 KB Output is correct
114 Correct 7 ms 7168 KB Output is correct
115 Correct 7 ms 7168 KB Output is correct
116 Correct 7 ms 7168 KB Output is correct
117 Correct 7 ms 7168 KB Output is correct
118 Correct 7 ms 7168 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 664 ms 38824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -