oj.uz

답안 #220958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
220958 2020-04-09T10:48:38 Z patrikpavic2 항공 노선도 (JOI18_airline) C++17
0 / 100
 1178 ms 168956 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];

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);
	vector < int > v;
	for(int i = 0;i < 5 * M;i++){
		v.PB(rand() % koliko); v.PB(rand() % koliko);
	}
	//printf("%d\n", v[0]);
	for(int i = 0;i < 10 * M;i += 2){
		//printf("mijenjam %d i %d\n", v[i], v[i + 1]);
		swap(imaa[v[i]], imaa[v[i + 1]]);
	}
}

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

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);
	vector < int > v;
	for(int i = 0;i < 5 * M;i++){
		v.PB(rand() % koliko2); v.PB(rand() % koliko2);
	}
	//printf("%d\n", v[0]);
	reverse(v.begin(), v.end());
	for(int i = 0;i < 10 * M;i += 2){
		//printf("mijenjam %d i %d\n", v[i], v[i + 1]);
		swap(ima[v[i]], ima[v[i + 1]]);
	}
}

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

Subtask #1
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 426 ms 138800 KB Output is correct
2 Correct 435 ms 138944 KB Output is correct
3 Correct 442 ms 138544 KB Output is correct
4 Correct 430 ms 138544 KB Output is correct
5 Correct 441 ms 138808 KB Output is correct
6 Correct 446 ms 138544 KB Output is correct
7 Correct 430 ms 138544 KB Output is correct
8 Correct 478 ms 138544 KB Output is correct
9 Correct 421 ms 138800 KB Output is correct
10 Correct 435 ms 139208 KB Output is correct
11 Correct 435 ms 138544 KB Output is correct
12 Correct 421 ms 138544 KB Output is correct
13 Correct 450 ms 139112 KB Output is correct
14 Correct 459 ms 138544 KB Output is correct
15 Correct 434 ms 138800 KB Output is correct
16 Correct 432 ms 138552 KB Output is correct
17 Correct 427 ms 138544 KB Output is correct
18 Correct 435 ms 138880 KB Output is correct
19 Correct 445 ms 138544 KB Output is correct
20 Correct 424 ms 138544 KB Output is correct
21 Correct 429 ms 138800 KB Output is correct
22 Correct 428 ms 138808 KB Output is correct
23 Correct 437 ms 138544 KB Output is correct
24 Correct 447 ms 138544 KB Output is correct
25 Correct 434 ms 138544 KB Output is correct
26 Correct 458 ms 138544 KB Output is correct
27 Correct 429 ms 138808 KB Output is correct
28 Correct 424 ms 138552 KB Output is correct
29 Correct 434 ms 138544 KB Output is correct
30 Correct 442 ms 138496 KB Output is correct
31 Correct 427 ms 138544 KB Output is correct
32 Correct 440 ms 138544 KB Output is correct
33 Correct 445 ms 138800 KB Output is correct
34 Correct 439 ms 138544 KB Output is correct
35 Correct 423 ms 138544 KB Output is correct
36 Correct 435 ms 138800 KB Output is correct
37 Correct 409 ms 138536 KB Output is correct
38 Correct 445 ms 138544 KB Output is correct
39 Correct 430 ms 138552 KB Output is correct
40 Correct 445 ms 138544 KB Output is correct
41 Correct 442 ms 138792 KB Output is correct
42 Correct 424 ms 138544 KB Output is correct
43 Correct 430 ms 138800 KB Output is correct
44 Correct 450 ms 138544 KB Output is correct
45 Correct 413 ms 138536 KB Output is correct
46 Correct 441 ms 138800 KB Output is correct
47 Correct 426 ms 138800 KB Output is correct
48 Correct 435 ms 138544 KB Output is correct
49 Correct 443 ms 138544 KB Output is correct
50 Correct 435 ms 138544 KB Output is correct
51 Runtime error 14 ms 6784 KB Execution killed with signal 8 (could be triggered by violating memory limits)
52 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 426 ms 138800 KB Output is correct
2 Correct 435 ms 138944 KB Output is correct
3 Correct 442 ms 138544 KB Output is correct
4 Correct 430 ms 138544 KB Output is correct
5 Correct 441 ms 138808 KB Output is correct
6 Correct 446 ms 138544 KB Output is correct
7 Correct 430 ms 138544 KB Output is correct
8 Correct 478 ms 138544 KB Output is correct
9 Correct 421 ms 138800 KB Output is correct
10 Correct 435 ms 139208 KB Output is correct
11 Correct 435 ms 138544 KB Output is correct
12 Correct 421 ms 138544 KB Output is correct
13 Correct 450 ms 139112 KB Output is correct
14 Correct 459 ms 138544 KB Output is correct
15 Correct 434 ms 138800 KB Output is correct
16 Correct 432 ms 138552 KB Output is correct
17 Correct 427 ms 138544 KB Output is correct
18 Correct 435 ms 138880 KB Output is correct
19 Correct 445 ms 138544 KB Output is correct
20 Correct 424 ms 138544 KB Output is correct
21 Correct 429 ms 138800 KB Output is correct
22 Correct 428 ms 138808 KB Output is correct
23 Correct 437 ms 138544 KB Output is correct
24 Correct 447 ms 138544 KB Output is correct
25 Correct 434 ms 138544 KB Output is correct
26 Correct 458 ms 138544 KB Output is correct
27 Correct 429 ms 138808 KB Output is correct
28 Correct 424 ms 138552 KB Output is correct
29 Correct 434 ms 138544 KB Output is correct
30 Correct 442 ms 138496 KB Output is correct
31 Correct 427 ms 138544 KB Output is correct
32 Correct 440 ms 138544 KB Output is correct
33 Correct 445 ms 138800 KB Output is correct
34 Correct 439 ms 138544 KB Output is correct
35 Correct 423 ms 138544 KB Output is correct
36 Correct 435 ms 138800 KB Output is correct
37 Correct 409 ms 138536 KB Output is correct
38 Correct 445 ms 138544 KB Output is correct
39 Correct 430 ms 138552 KB Output is correct
40 Correct 445 ms 138544 KB Output is correct
41 Correct 442 ms 138792 KB Output is correct
42 Correct 424 ms 138544 KB Output is correct
43 Correct 430 ms 138800 KB Output is correct
44 Correct 450 ms 138544 KB Output is correct
45 Correct 413 ms 138536 KB Output is correct
46 Correct 441 ms 138800 KB Output is correct
47 Correct 426 ms 138800 KB Output is correct
48 Correct 435 ms 138544 KB Output is correct
49 Correct 443 ms 138544 KB Output is correct
50 Correct 435 ms 138544 KB Output is correct
51 Runtime error 14 ms 6784 KB Execution killed with signal 8 (could be triggered by violating memory limits)
52 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1123 ms 168672 KB Output is correct : V - N = 12
2 Correct 992 ms 167084 KB Output is correct : V - N = 12
3 Correct 661 ms 163124 KB Output is correct : V - N = 12
4 Correct 454 ms 160876 KB Output is correct : V - N = 12
5 Correct 575 ms 162960 KB Output is correct : V - N = 12
6 Correct 883 ms 166176 KB Output is correct : V - N = 12
7 Correct 1131 ms 168500 KB Output is correct : V - N = 12
8 Correct 1037 ms 167864 KB Output is correct : V - N = 12
9 Correct 744 ms 164312 KB Output is correct : V - N = 12
10 Correct 505 ms 161268 KB Output is correct : V - N = 12
11 Correct 536 ms 161492 KB Output is correct : V - N = 12
12 Correct 849 ms 164904 KB Output is correct : V - N = 12
13 Correct 1133 ms 168176 KB Output is correct : V - N = 12
14 Correct 1159 ms 168264 KB Output is correct : V - N = 12
15 Correct 850 ms 165388 KB Output is correct : V - N = 12
16 Correct 550 ms 161872 KB Output is correct : V - N = 12
17 Correct 481 ms 160944 KB Output is correct : V - N = 12
18 Correct 727 ms 163768 KB Output is correct : V - N = 12
19 Correct 1008 ms 167528 KB Output is correct : V - N = 12
20 Correct 1109 ms 168644 KB Output is correct : V - N = 12
21 Correct 606 ms 148256 KB Output is correct : V - N = 12
22 Correct 569 ms 147768 KB Output is correct : V - N = 12
23 Correct 485 ms 146720 KB Output is correct : V - N = 12
24 Correct 437 ms 146284 KB Output is correct : V - N = 12
25 Correct 453 ms 146728 KB Output is correct : V - N = 12
26 Correct 563 ms 147444 KB Output is correct : V - N = 12
27 Correct 601 ms 148124 KB Output is correct : V - N = 12
28 Correct 618 ms 148100 KB Output is correct : V - N = 12
29 Correct 516 ms 147224 KB Output is correct : V - N = 12
30 Correct 438 ms 146304 KB Output is correct : V - N = 12
31 Correct 471 ms 157112 KB Output is correct : V - N = 12
32 Correct 473 ms 157088 KB Output is correct : V - N = 12
33 Correct 472 ms 157100 KB Output is correct : V - N = 12
34 Correct 458 ms 157056 KB Output is correct : V - N = 12
35 Correct 466 ms 157024 KB Output is correct : V - N = 12
36 Correct 1129 ms 168816 KB Output is correct : V - N = 12
37 Correct 1143 ms 168900 KB Output is correct : V - N = 12
38 Correct 1139 ms 168956 KB Output is correct : V - N = 12
39 Correct 1128 ms 168640 KB Output is correct : V - N = 12
40 Correct 1178 ms 168740 KB Output is correct : V - N = 12
41 Correct 582 ms 162212 KB Output is correct : V - N = 12
42 Correct 568 ms 162072 KB Output is correct : V - N = 12
43 Correct 552 ms 161876 KB Output is correct : V - N = 12
44 Correct 484 ms 160752 KB Output is correct : V - N = 12
45 Correct 536 ms 161664 KB Output is correct : V - N = 12
46 Correct 694 ms 163504 KB Output is correct : V - N = 12
47 Correct 609 ms 162092 KB Output is correct : V - N = 12
48 Correct 754 ms 164388 KB Output is correct : V - N = 12
49 Correct 509 ms 161328 KB Output is correct : V - N = 12
50 Correct 457 ms 161212 KB Output is correct : V - N = 12
51 Correct 972 ms 166932 KB Output is correct : V - N = 12
52 Correct 472 ms 160904 KB Output is correct : V - N = 12
53 Correct 885 ms 165640 KB Output is correct : V - N = 12
54 Correct 1060 ms 167264 KB Output is correct : V - N = 12
55 Correct 488 ms 161104 KB Output is correct : V - N = 12
56 Correct 796 ms 164280 KB Output is correct : V - N = 12
57 Correct 1064 ms 167844 KB Output is correct : V - N = 12
58 Correct 552 ms 161480 KB Output is correct : V - N = 12
59 Correct 708 ms 163256 KB Output is correct : V - N = 12
60 Correct 1111 ms 168008 KB Output is correct : V - N = 12
61 Correct 417 ms 139056 KB Output is correct : V - N = 12
62 Correct 429 ms 138976 KB Output is correct : V - N = 12
63 Correct 430 ms 139088 KB Output is correct : V - N = 12
64 Correct 466 ms 138800 KB Output is correct : V - N = 12
65 Correct 450 ms 139056 KB Output is correct : V - N = 12
66 Correct 436 ms 139064 KB Output is correct : V - N = 12
67 Correct 412 ms 139056 KB Output is correct : V - N = 12
68 Correct 416 ms 138808 KB Output is correct : V - N = 12
69 Correct 434 ms 138864 KB Output is correct : V - N = 12
70 Correct 422 ms 138792 KB Output is correct : V - N = 12
71 Correct 419 ms 139024 KB Output is correct : V - N = 12
72 Correct 442 ms 139056 KB Output is correct : V - N = 12
73 Correct 414 ms 138800 KB Output is correct : V - N = 12
74 Correct 428 ms 139056 KB Output is correct : V - N = 12
75 Correct 423 ms 138808 KB Output is correct : V - N = 12
76 Correct 437 ms 138808 KB Output is correct : V - N = 12
77 Correct 429 ms 138800 KB Output is correct : V - N = 12
78 Correct 422 ms 139056 KB Output is correct : V - N = 12
79 Correct 425 ms 139056 KB Output is correct : V - N = 12
80 Correct 419 ms 139056 KB Output is correct : V - N = 12
81 Correct 450 ms 138800 KB Output is correct : V - N = 12
82 Correct 442 ms 138928 KB Output is correct : V - N = 12
83 Correct 449 ms 138800 KB Output is correct : V - N = 12
84 Correct 450 ms 138784 KB Output is correct : V - N = 12
85 Correct 450 ms 138728 KB Output is correct : V - N = 12
86 Correct 441 ms 138792 KB Output is correct : V - N = 12
87 Correct 428 ms 138752 KB Output is correct : V - N = 12
88 Correct 442 ms 138800 KB Output is correct : V - N = 12
89 Correct 455 ms 138808 KB Output is correct : V - N = 12
90 Correct 480 ms 138904 KB Output is correct : V - N = 12
91 Correct 470 ms 138816 KB Output is correct : V - N = 12
92 Correct 434 ms 138760 KB Output is correct : V - N = 12
93 Correct 456 ms 139232 KB Output is correct : V - N = 12
94 Correct 441 ms 138800 KB Output is correct : V - N = 12
95 Correct 449 ms 138800 KB Output is correct : V - N = 12
96 Correct 441 ms 138800 KB Output is correct : V - N = 12
97 Correct 445 ms 139016 KB Output is correct : V - N = 12
98 Correct 437 ms 138984 KB Output is correct : V - N = 12
99 Correct 445 ms 139056 KB Output is correct : V - N = 12
100 Correct 436 ms 138944 KB Output is correct : V - N = 12
101 Correct 440 ms 139008 KB Output is correct : V - N = 12
102 Correct 431 ms 138800 KB Output is correct : V - N = 12
103 Correct 453 ms 138992 KB Output is correct : V - N = 12
104 Correct 462 ms 138880 KB Output is correct : V - N = 12
105 Correct 422 ms 138808 KB Output is correct : V - N = 12
106 Correct 438 ms 138800 KB Output is correct : V - N = 12
107 Correct 422 ms 138800 KB Output is correct : V - N = 12
108 Correct 413 ms 139056 KB Output is correct : V - N = 12
109 Correct 432 ms 138800 KB Output is correct : V - N = 12
110 Correct 416 ms 139056 KB Output is correct : V - N = 12
111 Correct 419 ms 139200 KB Output is correct : V - N = 12
112 Correct 415 ms 138800 KB Output is correct : V - N = 12
113 Correct 424 ms 138800 KB Output is correct : V - N = 12
114 Correct 431 ms 138800 KB Output is correct : V - N = 12
115 Correct 423 ms 138808 KB Output is correct : V - N = 12
116 Correct 427 ms 139056 KB Output is correct : V - N = 12
117 Correct 473 ms 138800 KB Output is correct : V - N = 12
118 Correct 427 ms 138800 KB Output is correct : V - N = 12
119 Correct 434 ms 139056 KB Output is correct : V - N = 12
120 Correct 426 ms 138800 KB Output is correct : V - N = 12
121 Correct 445 ms 138544 KB Output is correct : V - N = 12
122 Correct 439 ms 138544 KB Output is correct : V - N = 12
123 Correct 427 ms 138544 KB Output is correct : V - N = 12
124 Correct 436 ms 138544 KB Output is correct : V - N = 12
125 Correct 435 ms 138544 KB Output is correct : V - N = 12
126 Correct 425 ms 138544 KB Output is correct : V - N = 12
127 Correct 447 ms 138544 KB Output is correct : V - N = 12
128 Correct 430 ms 138552 KB Output is correct : V - N = 12
129 Correct 441 ms 138592 KB Output is correct : V - N = 12
130 Correct 433 ms 139056 KB Output is correct : V - N = 12
131 Correct 430 ms 138544 KB Output is correct : V - N = 12
132 Correct 436 ms 138544 KB Output is correct : V - N = 12
133 Correct 428 ms 138800 KB Output is correct : V - N = 12
134 Correct 425 ms 138800 KB Output is correct : V - N = 12
135 Correct 449 ms 138544 KB Output is correct : V - N = 12
136 Correct 441 ms 138800 KB Output is correct : V - N = 12
137 Correct 538 ms 138800 KB Output is correct : V - N = 12
138 Correct 426 ms 138800 KB Output is correct : V - N = 12
139 Correct 420 ms 138544 KB Output is correct : V - N = 12
140 Correct 428 ms 138544 KB Output is correct : V - N = 12
141 Correct 438 ms 139056 KB Output is correct : V - N = 12
142 Correct 425 ms 138544 KB Output is correct : V - N = 12
143 Correct 428 ms 138544 KB Output is correct : V - N = 12
144 Correct 423 ms 138800 KB Output is correct : V - N = 12
145 Correct 436 ms 138544 KB Output is correct : V - N = 12
146 Correct 440 ms 138544 KB Output is correct : V - N = 12
147 Correct 428 ms 138544 KB Output is correct : V - N = 12
148 Correct 426 ms 138800 KB Output is correct : V - N = 12
149 Correct 428 ms 138544 KB Output is correct : V - N = 12
150 Correct 437 ms 138544 KB Output is correct : V - N = 12
151 Correct 429 ms 138544 KB Output is correct : V - N = 12
152 Correct 433 ms 138544 KB Output is correct : V - N = 12
153 Correct 524 ms 138544 KB Output is correct : V - N = 12
154 Correct 433 ms 138552 KB Output is correct : V - N = 12
155 Correct 423 ms 138544 KB Output is correct : V - N = 12
156 Correct 434 ms 138800 KB Output is correct : V - N = 12
157 Correct 438 ms 138544 KB Output is correct : V - N = 12
158 Correct 436 ms 138800 KB Output is correct : V - N = 12
159 Correct 433 ms 138544 KB Output is correct : V - N = 12
160 Correct 436 ms 138800 KB Output is correct : V - N = 12
161 Correct 434 ms 138800 KB Output is correct : V - N = 12
162 Correct 429 ms 138800 KB Output is correct : V - N = 12
163 Correct 546 ms 138544 KB Output is correct : V - N = 12
164 Correct 445 ms 138800 KB Output is correct : V - N = 12
165 Correct 426 ms 138544 KB Output is correct : V - N = 12
166 Correct 456 ms 138544 KB Output is correct : V - N = 12
167 Correct 433 ms 138800 KB Output is correct : V - N = 12
168 Correct 430 ms 138736 KB Output is correct : V - N = 12
169 Correct 475 ms 138544 KB Output is correct : V - N = 12
170 Correct 435 ms 138544 KB Output is correct : V - N = 12
171 Runtime error 13 ms 6784 KB Execution killed with signal 8 (could be triggered by violating memory limits)
172 Halted 0 ms 0 KB -