Submission #220962

# Submission time Handle Problem Language Result Execution time Memory
220962 2020-04-09T10:55:50 Z patrikpavic2 Airline Route Map (JOI18_airline) C++17
0 / 100
824 ms 77000 KB
#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int N = 1055;
const int M = N * N;

typedef pair < int, int > pii;

int nnn, imaa[M], uk = 0, encode[N][N], koliko = 0;
int decodeA[M], decodeB[M];
vector < pii > bezveze;
int glp[N][N];
vector < int > v2;

void jako_glupo(){
	srand(123);
	for(int i = 0;i < 12;i++)
		for(int j = i + 1;j < 12;j++){
			glp[i][j] = glp[j][i] = rand() % 2;
			//if(glp[i][j]) printf("%d --- %d\n", i, j);
		}
}

void precompute(){
	for(int i = 0;i < nnn;i++){
		for(int j = i + 1;j < nnn;j++){
			encode[i][j] = koliko;
			encode[j][i] = koliko;
			decodeA[koliko] = i;
			decodeB[koliko] = j;
			koliko++;
		}
	}
}	

void zakompliciraj(){
	srand(69);
	for(int i = 0;i < M;i++){
		v2.PB(rand() % koliko); v2.PB(rand() % koliko);
	}
	for(int i = 0;i < 2 * M;i += 2){
		swap(imaa[v2[i]], imaa[v2[i + 1]]);
	}
	v2.clear();
}

void Alice( int nn, int mm, int A[], int B[] ){
	nnn = nn; precompute(); jako_glupo();
	for(int i = 0;i < mm;i++)
		imaa[encode[A[i]][B[i]]] = 1;
	zakompliciraj();
	for(int i = 0;i < nn * nn;i++){
		if(imaa[i]) bezveze.PB({decodeA[i], decodeB[i]});
	}
	for(int i = nn;i < nn + 12;i++){
		for(int j = 0;j < nn;j++){
			if((j & (1 << (i - nn))))
				bezveze.PB({i, j});
		}
		for(int j = 0;j < i - nn;j++){
			if(glp[i - nn][j])
				bezveze.PB({i, j + nn});
		}
	}
	InitG(nn + 12, (int)bezveze.size());
	for(int i = 0;i < (int)bezveze.size();i++){
		//printf("%d --- %d\n", bezveze[i].X, bezveze[i].Y);
		MakeG(i, bezveze[i].X, bezveze[i].Y);
	}
}
















#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;

const int N = 1055;
const int M = N * N;

int n2, m2, n, m, ima[M], spj[N][N], glp2[N][N];
int trb[N], poseban[N], prav[N];
int cur[N], tko[N], gotov = 0, poten[N], deg[N];
int encode2[N][N], koliko2;
int decodeA2[M], decodeB2[M];

vector < int > kand[N], v;

void jako_glupo2(){
	srand(123);
	for(int i = 0;i < 12;i++)
		for(int j = i + 1;j < 12;j++){
			glp2[i][j] = glp2[j][i] = rand() % 2;
			//if(glp2[i][j]) printf("%d --- %d\n", i, j);
		}
}

void precompute2(){
	for(int i = 0;i < n;i++){
		for(int j = i + 1;j < n;j++){
			encode2[i][j] = koliko2;
			encode2[j][i] = koliko2;
			decodeA2[koliko2] = i;
			decodeB2[koliko2] = j;
			koliko2++;
		}
	}
}	

void zakompliciraj_obrnuto(){
	srand(69);
	for(int i = 0;i < M;i++){
		v.PB(rand() % koliko2); v.PB(rand() % koliko2);
	}
	reverse(v.begin(), v.end());
	for(int i = 0;i < 2 * M;i += 2){
		swap(ima[v[i]], ima[v[i + 1]]);
	}
	v.clear();
}

void probaj(int i){
	if(i == 12){
		gotov = 1; return;
	}
	for(int x : kand[i]){
		if(poseban[x]) continue;
		int mogu = 1;
		for(int j = 0;j < i;j++)
			if(spj[x][tko[j]] != glp2[i][j])
				mogu = 0;
		if(!mogu) continue;
		tko[i] = x; poseban[x] = 1; poten[x] = i;
		probaj(i + 1);
		if(gotov) return;
		poseban[x] = 0;
	}
}

void Bob( int nn, int mm, int C[], int D[] ){
	n2 = nn; n = nn - 12; precompute2(); jako_glupo2();
	for(int i = 0;i < 12;i++){
		for(int j = 0;j < n;j++)
			trb[i] += !!(j & (1 << i));
		for(int j = 0;j < 12;j++)
			trb[i] += glp2[i][j];
	}
	for(int i = 0;i < mm;i++){
		deg[C[i]]++, deg[D[i]]++;
		//printf("%d --- %d\n", C[i], D[i]);
		spj[C[i]][D[i]] = 1; spj[D[i]][C[i]] = 1;
	}
	for(int i = 0;i < n2;i++){
		for(int j = 0;j < 12;j++){
			if(deg[i] == trb[j])
				kand[j].PB(i);// printf("%d kandidat za %d\n", i, j);
		}
	}
	probaj(0); //printf("gotov = %d\n", gotov);
	for(int i = 0;i < n2;i++){
		if(!poseban[i]) continue;
		//printf("POSEBAN : %d je %d\n", i, poten[i]);
		for(int j = 0;j < n2;j++){
			if(spj[i][j]) 
				prav[j] += (1 << poten[i]);
		}
	}
	for(int j = 0;j < n2;j++){
		if(poseban[j]) continue;
		//printf("%d ---> %d\n", j, prav[j]);
	}
	int uk = 0;
	for(int i = 0;i < mm;i++){
		if(poseban[C[i]]) continue;
		if(poseban[D[i]]) continue;
		ima[encode2[prav[C[i]]][prav[D[i]]]] = 1;
		//printf("%d --- %d tj. %d --- %d\n",C[i], D[i],prav[C[i]], prav[D[i]]);
		uk++;
	}
	zakompliciraj_obrnuto();
	InitMap(n, uk);
	for(int i = 0;i < M;i++){
		if(ima[i]) {
			//printf("spajam %d i %d\n", decodeA2[i], decodeB2[i]);
			MakeMap(decodeA2[i], decodeB2[i]); 
		}
	}
}




# Verdict Execution time Memory Grader output
1 Correct 107 ms 40120 KB Output is correct
2 Correct 104 ms 40064 KB Output is correct
3 Correct 101 ms 40112 KB Output is correct
4 Correct 105 ms 40096 KB Output is correct
5 Correct 107 ms 40096 KB Output is correct
6 Correct 101 ms 40096 KB Output is correct
7 Correct 103 ms 40120 KB Output is correct
8 Correct 101 ms 40048 KB Output is correct
9 Correct 102 ms 40096 KB Output is correct
10 Correct 99 ms 40128 KB Output is correct
11 Correct 115 ms 40112 KB Output is correct
12 Correct 105 ms 40120 KB Output is correct
13 Correct 101 ms 40112 KB Output is correct
14 Correct 101 ms 40112 KB Output is correct
15 Correct 103 ms 40112 KB Output is correct
16 Correct 104 ms 40112 KB Output is correct
17 Correct 106 ms 40120 KB Output is correct
18 Correct 108 ms 40112 KB Output is correct
19 Correct 104 ms 40096 KB Output is correct
20 Correct 103 ms 40144 KB Output is correct
21 Correct 109 ms 40352 KB Output is correct
22 Correct 102 ms 40120 KB Output is correct
23 Correct 100 ms 40112 KB Output is correct
24 Correct 104 ms 40112 KB Output is correct
25 Correct 103 ms 40112 KB Output is correct
26 Correct 99 ms 40120 KB Output is correct
27 Correct 102 ms 40112 KB Output is correct
28 Correct 103 ms 40128 KB Output is correct
29 Correct 101 ms 40112 KB Output is correct
30 Correct 104 ms 40096 KB Output is correct
31 Correct 102 ms 40112 KB Output is correct
32 Correct 103 ms 40128 KB Output is correct
33 Correct 103 ms 40368 KB Output is correct
34 Correct 107 ms 40216 KB Output is correct
35 Correct 100 ms 40112 KB Output is correct
36 Correct 102 ms 40112 KB Output is correct
37 Correct 104 ms 40096 KB Output is correct
38 Correct 101 ms 40072 KB Output is correct
39 Correct 107 ms 40096 KB Output is correct
40 Correct 101 ms 40128 KB Output is correct
41 Correct 104 ms 40096 KB Output is correct
42 Correct 104 ms 40128 KB Output is correct
43 Correct 103 ms 40112 KB Output is correct
44 Correct 102 ms 40112 KB Output is correct
45 Correct 100 ms 40112 KB Output is correct
46 Correct 103 ms 40120 KB Output is correct
47 Correct 111 ms 40112 KB Output is correct
48 Correct 103 ms 40112 KB Output is correct
49 Correct 102 ms 40120 KB Output is correct
50 Correct 99 ms 40120 KB Output is correct
51 Runtime error 13 ms 6784 KB Execution killed with signal 8 (could be triggered by violating memory limits)
52 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 107 ms 40120 KB Output is correct
2 Correct 104 ms 40064 KB Output is correct
3 Correct 101 ms 40112 KB Output is correct
4 Correct 105 ms 40096 KB Output is correct
5 Correct 107 ms 40096 KB Output is correct
6 Correct 101 ms 40096 KB Output is correct
7 Correct 103 ms 40120 KB Output is correct
8 Correct 101 ms 40048 KB Output is correct
9 Correct 102 ms 40096 KB Output is correct
10 Correct 99 ms 40128 KB Output is correct
11 Correct 115 ms 40112 KB Output is correct
12 Correct 105 ms 40120 KB Output is correct
13 Correct 101 ms 40112 KB Output is correct
14 Correct 101 ms 40112 KB Output is correct
15 Correct 103 ms 40112 KB Output is correct
16 Correct 104 ms 40112 KB Output is correct
17 Correct 106 ms 40120 KB Output is correct
18 Correct 108 ms 40112 KB Output is correct
19 Correct 104 ms 40096 KB Output is correct
20 Correct 103 ms 40144 KB Output is correct
21 Correct 109 ms 40352 KB Output is correct
22 Correct 102 ms 40120 KB Output is correct
23 Correct 100 ms 40112 KB Output is correct
24 Correct 104 ms 40112 KB Output is correct
25 Correct 103 ms 40112 KB Output is correct
26 Correct 99 ms 40120 KB Output is correct
27 Correct 102 ms 40112 KB Output is correct
28 Correct 103 ms 40128 KB Output is correct
29 Correct 101 ms 40112 KB Output is correct
30 Correct 104 ms 40096 KB Output is correct
31 Correct 102 ms 40112 KB Output is correct
32 Correct 103 ms 40128 KB Output is correct
33 Correct 103 ms 40368 KB Output is correct
34 Correct 107 ms 40216 KB Output is correct
35 Correct 100 ms 40112 KB Output is correct
36 Correct 102 ms 40112 KB Output is correct
37 Correct 104 ms 40096 KB Output is correct
38 Correct 101 ms 40072 KB Output is correct
39 Correct 107 ms 40096 KB Output is correct
40 Correct 101 ms 40128 KB Output is correct
41 Correct 104 ms 40096 KB Output is correct
42 Correct 104 ms 40128 KB Output is correct
43 Correct 103 ms 40112 KB Output is correct
44 Correct 102 ms 40112 KB Output is correct
45 Correct 100 ms 40112 KB Output is correct
46 Correct 103 ms 40120 KB Output is correct
47 Correct 111 ms 40112 KB Output is correct
48 Correct 103 ms 40112 KB Output is correct
49 Correct 102 ms 40120 KB Output is correct
50 Correct 99 ms 40120 KB Output is correct
51 Runtime error 13 ms 6784 KB Execution killed with signal 8 (could be triggered by violating memory limits)
52 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 783 ms 76504 KB Output is correct : V - N = 12
2 Correct 631 ms 71160 KB Output is correct : V - N = 12
3 Correct 319 ms 64708 KB Output is correct : V - N = 12
4 Correct 130 ms 62420 KB Output is correct : V - N = 12
5 Correct 266 ms 63648 KB Output is correct : V - N = 12
6 Correct 561 ms 68876 KB Output is correct : V - N = 12
7 Correct 824 ms 76040 KB Output is correct : V - N = 12
8 Correct 716 ms 74104 KB Output is correct : V - N = 12
9 Correct 419 ms 65696 KB Output is correct : V - N = 12
10 Correct 165 ms 62748 KB Output is correct : V - N = 12
11 Correct 180 ms 63028 KB Output is correct : V - N = 12
12 Correct 461 ms 66224 KB Output is correct : V - N = 12
13 Correct 734 ms 74656 KB Output is correct : V - N = 12
14 Correct 757 ms 75400 KB Output is correct : V - N = 12
15 Correct 507 ms 67852 KB Output is correct : V - N = 12
16 Correct 220 ms 63280 KB Output is correct : V - N = 12
17 Correct 134 ms 62684 KB Output is correct : V - N = 12
18 Correct 381 ms 65196 KB Output is correct : V - N = 12
19 Correct 699 ms 72608 KB Output is correct : V - N = 12
20 Correct 776 ms 76336 KB Output is correct : V - N = 12
21 Correct 281 ms 49588 KB Output is correct : V - N = 12
22 Correct 237 ms 49064 KB Output is correct : V - N = 12
23 Correct 161 ms 48384 KB Output is correct : V - N = 12
24 Correct 114 ms 47740 KB Output is correct : V - N = 12
25 Correct 134 ms 48048 KB Output is correct : V - N = 12
26 Correct 224 ms 48972 KB Output is correct : V - N = 12
27 Correct 284 ms 49596 KB Output is correct : V - N = 12
28 Correct 270 ms 49700 KB Output is correct : V - N = 12
29 Correct 190 ms 48632 KB Output is correct : V - N = 12
30 Correct 118 ms 47808 KB Output is correct : V - N = 12
31 Correct 124 ms 58668 KB Output is correct : V - N = 12
32 Correct 122 ms 58428 KB Output is correct : V - N = 12
33 Correct 123 ms 58672 KB Output is correct : V - N = 12
34 Correct 127 ms 58432 KB Output is correct : V - N = 12
35 Correct 124 ms 58428 KB Output is correct : V - N = 12
36 Correct 796 ms 76456 KB Output is correct : V - N = 12
37 Correct 774 ms 77000 KB Output is correct : V - N = 12
38 Correct 813 ms 76832 KB Output is correct : V - N = 12
39 Correct 804 ms 76824 KB Output is correct : V - N = 12
40 Correct 804 ms 76496 KB Output is correct : V - N = 12
41 Correct 244 ms 63672 KB Output is correct : V - N = 12
42 Correct 215 ms 63368 KB Output is correct : V - N = 12
43 Correct 237 ms 63448 KB Output is correct : V - N = 12
44 Correct 124 ms 62084 KB Output is correct : V - N = 12
45 Correct 188 ms 63116 KB Output is correct : V - N = 12
46 Correct 339 ms 64944 KB Output is correct : V - N = 12
47 Correct 251 ms 63532 KB Output is correct : V - N = 12
48 Correct 431 ms 65852 KB Output is correct : V - N = 12
49 Correct 174 ms 62928 KB Output is correct : V - N = 12
50 Correct 132 ms 62532 KB Output is correct : V - N = 12
51 Correct 664 ms 71016 KB Output is correct : V - N = 12
52 Correct 131 ms 62520 KB Output is correct : V - N = 12
53 Correct 548 ms 68620 KB Output is correct : V - N = 12
54 Correct 698 ms 72928 KB Output is correct : V - N = 12
55 Correct 159 ms 62520 KB Output is correct : V - N = 12
56 Correct 449 ms 65768 KB Output is correct : V - N = 12
57 Correct 751 ms 74472 KB Output is correct : V - N = 12
58 Correct 208 ms 63188 KB Output is correct : V - N = 12
59 Correct 368 ms 64912 KB Output is correct : V - N = 12
60 Correct 770 ms 75168 KB Output is correct : V - N = 12
61 Correct 98 ms 40376 KB Output is correct : V - N = 12
62 Correct 114 ms 40888 KB Output is correct : V - N = 12
63 Correct 101 ms 40368 KB Output is correct : V - N = 12
64 Correct 101 ms 40376 KB Output is correct : V - N = 12
65 Correct 106 ms 40368 KB Output is correct : V - N = 12
66 Correct 104 ms 40640 KB Output is correct : V - N = 12
67 Correct 103 ms 40384 KB Output is correct : V - N = 12
68 Correct 101 ms 40376 KB Output is correct : V - N = 12
69 Correct 100 ms 40368 KB Output is correct : V - N = 12
70 Correct 99 ms 40368 KB Output is correct : V - N = 12
71 Correct 102 ms 40368 KB Output is correct : V - N = 12
72 Correct 106 ms 40616 KB Output is correct : V - N = 12
73 Correct 99 ms 40368 KB Output is correct : V - N = 12
74 Correct 100 ms 40368 KB Output is correct : V - N = 12
75 Correct 101 ms 40368 KB Output is correct : V - N = 12
76 Correct 101 ms 40376 KB Output is correct : V - N = 12
77 Correct 100 ms 40352 KB Output is correct : V - N = 12
78 Correct 101 ms 40376 KB Output is correct : V - N = 12
79 Correct 101 ms 40352 KB Output is correct : V - N = 12
80 Correct 104 ms 40376 KB Output is correct : V - N = 12
81 Correct 100 ms 40352 KB Output is correct : V - N = 12
82 Correct 102 ms 40376 KB Output is correct : V - N = 12
83 Correct 99 ms 40376 KB Output is correct : V - N = 12
84 Correct 99 ms 40400 KB Output is correct : V - N = 12
85 Correct 105 ms 40392 KB Output is correct : V - N = 12
86 Correct 101 ms 40384 KB Output is correct : V - N = 12
87 Correct 101 ms 40368 KB Output is correct : V - N = 12
88 Correct 107 ms 40384 KB Output is correct : V - N = 12
89 Correct 100 ms 40368 KB Output is correct : V - N = 12
90 Correct 98 ms 40368 KB Output is correct : V - N = 12
91 Correct 101 ms 40368 KB Output is correct : V - N = 12
92 Correct 109 ms 40368 KB Output is correct : V - N = 12
93 Correct 101 ms 40376 KB Output is correct : V - N = 12
94 Correct 104 ms 40376 KB Output is correct : V - N = 12
95 Correct 102 ms 40832 KB Output is correct : V - N = 12
96 Correct 102 ms 40400 KB Output is correct : V - N = 12
97 Correct 102 ms 40376 KB Output is correct : V - N = 12
98 Correct 106 ms 40384 KB Output is correct : V - N = 12
99 Correct 101 ms 40384 KB Output is correct : V - N = 12
100 Correct 103 ms 40368 KB Output is correct : V - N = 12
101 Correct 102 ms 40472 KB Output is correct : V - N = 12
102 Correct 97 ms 40368 KB Output is correct : V - N = 12
103 Correct 105 ms 40376 KB Output is correct : V - N = 12
104 Correct 109 ms 40368 KB Output is correct : V - N = 12
105 Correct 101 ms 40368 KB Output is correct : V - N = 12
106 Correct 104 ms 40536 KB Output is correct : V - N = 12
107 Correct 102 ms 40384 KB Output is correct : V - N = 12
108 Correct 106 ms 40640 KB Output is correct : V - N = 12
109 Correct 104 ms 40384 KB Output is correct : V - N = 12
110 Correct 101 ms 40376 KB Output is correct : V - N = 12
111 Correct 100 ms 40360 KB Output is correct : V - N = 12
112 Correct 98 ms 40352 KB Output is correct : V - N = 12
113 Correct 105 ms 40368 KB Output is correct : V - N = 12
114 Correct 98 ms 40352 KB Output is correct : V - N = 12
115 Correct 104 ms 40360 KB Output is correct : V - N = 12
116 Correct 105 ms 40368 KB Output is correct : V - N = 12
117 Correct 108 ms 40368 KB Output is correct : V - N = 12
118 Correct 108 ms 40384 KB Output is correct : V - N = 12
119 Correct 100 ms 40320 KB Output is correct : V - N = 12
120 Correct 103 ms 40400 KB Output is correct : V - N = 12
121 Correct 102 ms 40112 KB Output is correct : V - N = 12
122 Correct 101 ms 40120 KB Output is correct : V - N = 12
123 Correct 100 ms 40128 KB Output is correct : V - N = 12
124 Correct 104 ms 40112 KB Output is correct : V - N = 12
125 Correct 112 ms 40112 KB Output is correct : V - N = 12
126 Correct 97 ms 40120 KB Output is correct : V - N = 12
127 Correct 100 ms 40160 KB Output is correct : V - N = 12
128 Correct 101 ms 40112 KB Output is correct : V - N = 12
129 Correct 105 ms 40120 KB Output is correct : V - N = 12
130 Correct 100 ms 40144 KB Output is correct : V - N = 12
131 Correct 102 ms 40112 KB Output is correct : V - N = 12
132 Correct 99 ms 40112 KB Output is correct : V - N = 12
133 Correct 99 ms 40112 KB Output is correct : V - N = 12
134 Correct 98 ms 40120 KB Output is correct : V - N = 12
135 Correct 104 ms 40096 KB Output is correct : V - N = 12
136 Correct 102 ms 40064 KB Output is correct : V - N = 12
137 Correct 102 ms 40112 KB Output is correct : V - N = 12
138 Correct 109 ms 40112 KB Output is correct : V - N = 12
139 Correct 104 ms 40120 KB Output is correct : V - N = 12
140 Correct 104 ms 40112 KB Output is correct : V - N = 12
141 Correct 103 ms 40112 KB Output is correct : V - N = 12
142 Correct 104 ms 40112 KB Output is correct : V - N = 12
143 Correct 99 ms 40208 KB Output is correct : V - N = 12
144 Correct 104 ms 40112 KB Output is correct : V - N = 12
145 Correct 106 ms 40128 KB Output is correct : V - N = 12
146 Correct 104 ms 40096 KB Output is correct : V - N = 12
147 Correct 100 ms 40080 KB Output is correct : V - N = 12
148 Correct 99 ms 40112 KB Output is correct : V - N = 12
149 Correct 105 ms 40096 KB Output is correct : V - N = 12
150 Correct 104 ms 40112 KB Output is correct : V - N = 12
151 Correct 102 ms 40112 KB Output is correct : V - N = 12
152 Correct 104 ms 40096 KB Output is correct : V - N = 12
153 Correct 101 ms 40112 KB Output is correct : V - N = 12
154 Correct 100 ms 40096 KB Output is correct : V - N = 12
155 Correct 106 ms 40096 KB Output is correct : V - N = 12
156 Correct 110 ms 40096 KB Output is correct : V - N = 12
157 Correct 98 ms 40112 KB Output is correct : V - N = 12
158 Correct 107 ms 40112 KB Output is correct : V - N = 12
159 Correct 100 ms 40120 KB Output is correct : V - N = 12
160 Correct 103 ms 40112 KB Output is correct : V - N = 12
161 Correct 102 ms 40096 KB Output is correct : V - N = 12
162 Correct 115 ms 40368 KB Output is correct : V - N = 12
163 Correct 103 ms 40096 KB Output is correct : V - N = 12
164 Correct 107 ms 40120 KB Output is correct : V - N = 12
165 Correct 100 ms 40120 KB Output is correct : V - N = 12
166 Correct 107 ms 40120 KB Output is correct : V - N = 12
167 Correct 105 ms 40112 KB Output is correct : V - N = 12
168 Correct 102 ms 40120 KB Output is correct : V - N = 12
169 Correct 103 ms 40096 KB Output is correct : V - N = 12
170 Correct 100 ms 40112 KB Output is correct : V - N = 12
171 Runtime error 14 ms 6784 KB Execution killed with signal 8 (could be triggered by violating memory limits)
172 Halted 0 ms 0 KB -