oj.uz

Submission #56682

# Submission time Handle Problem Language Result Execution time Memory
56682 2018-07-12T07:17:26 Z 김세빈(#1617) Airline Route Map (JOI18_airline) C++11
0 / 100
 711 ms 30808 KB 
#include "Alicelib.h"
#include <cassert>
#include <cstdio>

#include <bits/stdc++.h>

using namespace std;

static int I[1100];

static void makeindex()
{
	int i;
	
	for(i=0;i<1024;i++) I[i] = i;
	
	sort(I, I+1024, [&](int a, int b){
		int i, c1, c2;
		for(i=c1=c2=0;i<10;i++){
			if(a & (1<<i)) c1 ++;
			if(b & (1<<i)) c2 ++;
		}
		if(c1 != c2) return c1 > c2;
		return a < b;
	});
	
	swap(I[2], I[11]);
}

void Alice(int N, int M, int A[], int B[])
{
	if(N == 1){
		InitG(1, 0);
		return;
	}
	if(N == 2){
		InitG(2, M);
	}
	
	int i, j, u;
	vector <int> G[1100];
	
	u = 0;
	
	makeindex();
	
	for(i=0;i<M;i++){
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
		u ++;
	}
	
	for(i=0;i<N;i++){
		for(j=0;j<10;j++){
			if(I[i] & (1<<j)){
				G[i].push_back(N+j);
				G[N+j].push_back(i);
				u ++;
			}
		}
		G[i].push_back(N+11);
		G[N+11].push_back(i);
		u ++;
	}
	
	for(i=N;i<=N+10;i++){
		G[i].push_back(i+1);
		G[i+1].push_back(i);
		u ++;
	}
	
	InitG(N+12, u);
	
	int f = 0;
	
	for(i=0;i<N+12;i++){
		for(auto p: G[i]){
			if(p > i) MakeG(f++, i, p);
		}
	}
}


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

#include <bits/stdc++.h>

using namespace std;

static int I[1100], K[1100], P[1100];
static bool chk[1100];

static void makeindex()
{
	int i;
	
	for(i=0;i<1024;i++) I[i] = i;
	
	sort(I, I+1024, [&](int a, int b){
		int i, c1, c2;
		for(i=c1=c2=0;i<10;i++){
			if(a & (1<<i)) c1 ++;
			if(b & (1<<i)) c2 ++;
		}
		if(c1 != c2) return c1 > c2;
		return a < b;
	});
	
	swap(I[2], I[11]);
	
	for(i=0;i<1024;i++) K[I[i]] = i;
}


void Bob( int V, int U, int C[], int D[])
{
	if(V == 1){
		InitMap(1, 0);
		return;
	}
	if(V == 2){
		if(U == 1){
			InitMap(2, 1);
			MakeMap(0, 1);
		}
		else{
			InitMap(2, 0);
		}
		return;
	}
	
	vector <int> G[1100];
	int i, c, n_11, n_10, T[12], m;
	
	m = 0;
	
	for(i=0;i<U;i++){
		G[C[i]].push_back(D[i]);
		G[D[i]].push_back(C[i]);
	}
	
	makeindex();
	
	int f = 0;
	
	for(i=0;i<V;i++){
		if(G[i].size() == 2) break;
	}
	
	n_10 = i;
	
	if(G[G[n_10][0]].size() < G[G[n_10][1]].size()) n_11 = G[n_10][1], T[9] = G[n_10][0];
	else n_11 = G[n_10][0], T[9] = G[n_10][1];
	
	for(auto p: G[n_11]){
		if(p != n_10) chk[p] = 1;
	}
	
	T[10] = n_10;
	
	P[T[9]] = 1<<9;
	
	for(i=8;i>=0;i--){
		for(auto p: G[T[i+1]]){
			if(!chk[p] && p != T[i+2]){
				T[i] = p;
				break;
			}
		}
		P[T[i]] = 1<<i;
	}
	
//	for(i=0;i<=9;i++) printf("%d ",T[i]);
//	printf("\n");
	
//	printf("%d %d\n", n_10, n_11);
	
	for(i=0;i<V;i++){
		if(chk[i]){
			c = 0;
			for(auto p: G[i]){
				if(chk[p]) m ++;
				else if(p != n_11){
					c |= P[p];
				}
			}
//			printf("%d : %d\n", i, c);
			I[i] = K[c];
		}
	}
	
	InitMap(V-12, m/2);
	
	for(i=0;i<V;i++){
		if(chk[i]){
			for(auto p: G[i]){
				if(chk[p] && i < p){
					MakeMap(I[i], I[p]);
				}
			}
		}
	}
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:63:6: warning: unused variable 'f' [-Wunused-variable]
  int f = 0;
      ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6840 KB Output is correct
2 Correct 8 ms 6640 KB Output is correct
3 Correct 8 ms 6640 KB Output is correct
4 Correct 8 ms 6896 KB Output is correct
5 Correct 8 ms 6648 KB Output is correct
6 Correct 8 ms 6640 KB Output is correct
7 Correct 8 ms 6784 KB Output is correct
8 Correct 8 ms 6896 KB Output is correct
9 Correct 8 ms 6736 KB Output is correct
10 Correct 8 ms 6640 KB Output is correct
11 Correct 8 ms 6896 KB Output is correct
12 Correct 8 ms 6648 KB Output is correct
13 Correct 8 ms 6640 KB Output is correct
14 Correct 8 ms 6640 KB Output is correct
15 Correct 8 ms 6640 KB Output is correct
16 Correct 8 ms 6640 KB Output is correct
17 Correct 8 ms 6896 KB Output is correct
18 Correct 8 ms 6664 KB Output is correct
19 Correct 9 ms 6640 KB Output is correct
20 Correct 8 ms 6640 KB Output is correct
21 Correct 8 ms 6896 KB Output is correct
22 Correct 8 ms 6648 KB Output is correct
23 Correct 8 ms 6736 KB Output is correct
24 Correct 8 ms 6640 KB Output is correct
25 Correct 8 ms 6984 KB Output is correct
26 Correct 8 ms 6736 KB Output is correct
27 Correct 8 ms 6696 KB Output is correct
28 Correct 8 ms 6648 KB Output is correct
29 Correct 8 ms 6640 KB Output is correct
30 Correct 8 ms 6640 KB Output is correct
31 Correct 8 ms 6640 KB Output is correct
32 Correct 8 ms 6640 KB Output is correct
33 Correct 8 ms 6896 KB Output is correct
34 Correct 8 ms 6640 KB Output is correct
35 Correct 8 ms 6640 KB Output is correct
36 Correct 8 ms 6728 KB Output is correct
37 Correct 8 ms 6896 KB Output is correct
38 Correct 8 ms 6640 KB Output is correct
39 Correct 8 ms 6640 KB Output is correct
40 Correct 8 ms 6648 KB Output is correct
41 Correct 8 ms 6640 KB Output is correct
42 Correct 8 ms 6896 KB Output is correct
43 Correct 8 ms 6640 KB Output is correct
44 Correct 8 ms 6640 KB Output is correct
45 Correct 8 ms 6640 KB Output is correct
46 Correct 8 ms 6896 KB Output is correct
47 Correct 8 ms 6640 KB Output is correct
48 Correct 8 ms 6640 KB Output is correct
49 Correct 8 ms 6640 KB Output is correct
50 Correct 8 ms 6896 KB Output is correct
51 Correct 7 ms 6640 KB Output is correct
52 Incorrect 5 ms 3320 KB Wrong Answer [6]
53 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6840 KB Output is correct
2 Correct 8 ms 6640 KB Output is correct
3 Correct 8 ms 6640 KB Output is correct
4 Correct 8 ms 6896 KB Output is correct
5 Correct 8 ms 6648 KB Output is correct
6 Correct 8 ms 6640 KB Output is correct
7 Correct 8 ms 6784 KB Output is correct
8 Correct 8 ms 6896 KB Output is correct
9 Correct 8 ms 6736 KB Output is correct
10 Correct 8 ms 6640 KB Output is correct
11 Correct 8 ms 6896 KB Output is correct
12 Correct 8 ms 6648 KB Output is correct
13 Correct 8 ms 6640 KB Output is correct
14 Correct 8 ms 6640 KB Output is correct
15 Correct 8 ms 6640 KB Output is correct
16 Correct 8 ms 6640 KB Output is correct
17 Correct 8 ms 6896 KB Output is correct
18 Correct 8 ms 6664 KB Output is correct
19 Correct 9 ms 6640 KB Output is correct
20 Correct 8 ms 6640 KB Output is correct
21 Correct 8 ms 6896 KB Output is correct
22 Correct 8 ms 6648 KB Output is correct
23 Correct 8 ms 6736 KB Output is correct
24 Correct 8 ms 6640 KB Output is correct
25 Correct 8 ms 6984 KB Output is correct
26 Correct 8 ms 6736 KB Output is correct
27 Correct 8 ms 6696 KB Output is correct
28 Correct 8 ms 6648 KB Output is correct
29 Correct 8 ms 6640 KB Output is correct
30 Correct 8 ms 6640 KB Output is correct
31 Correct 8 ms 6640 KB Output is correct
32 Correct 8 ms 6640 KB Output is correct
33 Correct 8 ms 6896 KB Output is correct
34 Correct 8 ms 6640 KB Output is correct
35 Correct 8 ms 6640 KB Output is correct
36 Correct 8 ms 6728 KB Output is correct
37 Correct 8 ms 6896 KB Output is correct
38 Correct 8 ms 6640 KB Output is correct
39 Correct 8 ms 6640 KB Output is correct
40 Correct 8 ms 6648 KB Output is correct
41 Correct 8 ms 6640 KB Output is correct
42 Correct 8 ms 6896 KB Output is correct
43 Correct 8 ms 6640 KB Output is correct
44 Correct 8 ms 6640 KB Output is correct
45 Correct 8 ms 6640 KB Output is correct
46 Correct 8 ms 6896 KB Output is correct
47 Correct 8 ms 6640 KB Output is correct
48 Correct 8 ms 6640 KB Output is correct
49 Correct 8 ms 6640 KB Output is correct
50 Correct 8 ms 6896 KB Output is correct
51 Correct 7 ms 6640 KB Output is correct
52 Incorrect 5 ms 3320 KB Wrong Answer [6]
53 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 30520 KB Output is correct : V - N = 12
2 Correct 546 ms 27688 KB Output is correct : V - N = 12
3 Correct 212 ms 15968 KB Output is correct : V - N = 12
4 Correct 14 ms 7544 KB Output is correct : V - N = 12
5 Correct 124 ms 11808 KB Output is correct : V - N = 12
6 Correct 463 ms 25608 KB Output is correct : V - N = 12
7 Correct 659 ms 30808 KB Output is correct : V - N = 12
8 Correct 592 ms 29200 KB Output is correct : V - N = 12
9 Correct 280 ms 18096 KB Output is correct : V - N = 12
10 Correct 40 ms 8288 KB Output is correct : V - N = 12
11 Correct 67 ms 9400 KB Output is correct : V - N = 12
12 Correct 313 ms 21080 KB Output is correct : V - N = 12
13 Correct 608 ms 29784 KB Output is correct : V - N = 12
14 Correct 654 ms 30440 KB Output is correct : V - N = 12
15 Correct 392 ms 24504 KB Output is correct : V - N = 12
16 Correct 88 ms 10576 KB Output is correct : V - N = 12
17 Correct 19 ms 7648 KB Output is correct : V - N = 12
18 Correct 299 ms 17048 KB Output is correct : V - N = 12
19 Correct 492 ms 28672 KB Output is correct : V - N = 12
20 Correct 642 ms 30808 KB Output is correct : V - N = 12
21 Correct 194 ms 15048 KB Output is correct : V - N = 12
22 Correct 137 ms 12152 KB Output is correct : V - N = 12
23 Correct 63 ms 9200 KB Output is correct : V - N = 12
24 Correct 10 ms 7000 KB Output is correct : V - N = 12
25 Correct 39 ms 8256 KB Output is correct : V - N = 12
26 Correct 118 ms 11752 KB Output is correct : V - N = 12
27 Correct 180 ms 13040 KB Output is correct : V - N = 12
28 Correct 114 ms 12800 KB Output is correct : V - N = 12
29 Correct 74 ms 9864 KB Output is correct : V - N = 12
30 Correct 17 ms 7248 KB Output is correct : V - N = 12
31 Correct 13 ms 6992 KB Output is correct : V - N = 12
32 Correct 13 ms 7152 KB Output is correct : V - N = 12
33 Correct 12 ms 7080 KB Output is correct : V - N = 12
34 Correct 13 ms 7072 KB Output is correct : V - N = 12
35 Correct 13 ms 7160 KB Output is correct : V - N = 12
36 Correct 679 ms 30576 KB Output is correct : V - N = 12
37 Correct 682 ms 30560 KB Output is correct : V - N = 12
38 Correct 711 ms 30632 KB Output is correct : V - N = 12
39 Correct 691 ms 30528 KB Output is correct : V - N = 12
40 Correct 661 ms 30616 KB Output is correct : V - N = 12
41 Correct 142 ms 11656 KB Output is correct : V - N = 12
42 Correct 123 ms 10800 KB Output is correct : V - N = 12
43 Correct 115 ms 11456 KB Output is correct : V - N = 12
44 Correct 13 ms 7408 KB Output is correct : V - N = 12
45 Correct 76 ms 9296 KB Output is correct : V - N = 12
46 Correct 214 ms 16368 KB Output is correct : V - N = 12
47 Correct 118 ms 11568 KB Output is correct : V - N = 12
48 Correct 290 ms 18008 KB Output is correct : V - N = 12
49 Correct 75 ms 9200 KB Output is correct : V - N = 12
50 Correct 26 ms 7712 KB Output is correct : V - N = 12
51 Correct 502 ms 27624 KB Output is correct : V - N = 12
52 Correct 14 ms 7408 KB Output is correct : V - N = 12
53 Correct 423 ms 25584 KB Output is correct : V - N = 12
54 Correct 568 ms 28816 KB Output is correct : V - N = 12
55 Correct 38 ms 8096 KB Output is correct : V - N = 12
56 Correct 360 ms 20304 KB Output is correct : V - N = 12
57 Correct 651 ms 29752 KB Output is correct : V - N = 12
58 Correct 89 ms 10440 KB Output is correct : V - N = 12
59 Correct 286 ms 16864 KB Output is correct : V - N = 12
60 Correct 659 ms 30320 KB Output is correct : V - N = 12
61 Correct 8 ms 6896 KB Output is correct : V - N = 12
62 Correct 9 ms 6896 KB Output is correct : V - N = 12
63 Correct 9 ms 6736 KB Output is correct : V - N = 12
64 Correct 8 ms 6640 KB Output is correct : V - N = 12
65 Correct 8 ms 6640 KB Output is correct : V - N = 12
66 Correct 8 ms 6896 KB Output is correct : V - N = 12
67 Correct 8 ms 6896 KB Output is correct : V - N = 12
68 Correct 8 ms 6896 KB Output is correct : V - N = 12
69 Correct 9 ms 6640 KB Output is correct : V - N = 12
70 Correct 9 ms 6640 KB Output is correct : V - N = 12
71 Correct 8 ms 6640 KB Output is correct : V - N = 12
72 Correct 8 ms 6896 KB Output is correct : V - N = 12
73 Correct 8 ms 6896 KB Output is correct : V - N = 12
74 Correct 17 ms 6896 KB Output is correct : V - N = 12
75 Correct 8 ms 6896 KB Output is correct : V - N = 12
76 Correct 8 ms 6872 KB Output is correct : V - N = 12
77 Correct 8 ms 6640 KB Output is correct : V - N = 12
78 Correct 8 ms 6936 KB Output is correct : V - N = 12
79 Correct 8 ms 6736 KB Output is correct : V - N = 12
80 Correct 8 ms 6896 KB Output is correct : V - N = 12
81 Correct 8 ms 6896 KB Output is correct : V - N = 12
82 Correct 8 ms 6640 KB Output is correct : V - N = 12
83 Correct 8 ms 6896 KB Output is correct : V - N = 12
84 Correct 8 ms 6640 KB Output is correct : V - N = 12
85 Correct 8 ms 6640 KB Output is correct : V - N = 12
86 Correct 8 ms 6904 KB Output is correct : V - N = 12
87 Correct 8 ms 6896 KB Output is correct : V - N = 12
88 Correct 8 ms 6896 KB Output is correct : V - N = 12
89 Correct 8 ms 6640 KB Output is correct : V - N = 12
90 Correct 8 ms 6896 KB Output is correct : V - N = 12
91 Correct 8 ms 6648 KB Output is correct : V - N = 12
92 Correct 8 ms 6640 KB Output is correct : V - N = 12
93 Correct 8 ms 6640 KB Output is correct : V - N = 12
94 Correct 6 ms 6640 KB Output is correct : V - N = 12
95 Correct 8 ms 6640 KB Output is correct : V - N = 12
96 Correct 8 ms 6896 KB Output is correct : V - N = 12
97 Correct 8 ms 6696 KB Output is correct : V - N = 12
98 Correct 8 ms 6736 KB Output is correct : V - N = 12
99 Correct 8 ms 6736 KB Output is correct : V - N = 12
100 Correct 9 ms 6776 KB Output is correct : V - N = 12
101 Correct 8 ms 6648 KB Output is correct : V - N = 12
102 Correct 8 ms 6736 KB Output is correct : V - N = 12
103 Correct 17 ms 6640 KB Output is correct : V - N = 12
104 Correct 8 ms 6736 KB Output is correct : V - N = 12
105 Correct 8 ms 6640 KB Output is correct : V - N = 12
106 Correct 9 ms 6736 KB Output is correct : V - N = 12
107 Correct 9 ms 6896 KB Output is correct : V - N = 12
108 Correct 9 ms 6896 KB Output is correct : V - N = 12
109 Correct 8 ms 6640 KB Output is correct : V - N = 12
110 Correct 8 ms 6840 KB Output is correct : V - N = 12
111 Correct 9 ms 6896 KB Output is correct : V - N = 12
112 Correct 8 ms 6640 KB Output is correct : V - N = 12
113 Correct 8 ms 6640 KB Output is correct : V - N = 12
114 Correct 8 ms 6896 KB Output is correct : V - N = 12
115 Correct 9 ms 6640 KB Output is correct : V - N = 12
116 Correct 9 ms 6640 KB Output is correct : V - N = 12
117 Correct 8 ms 6896 KB Output is correct : V - N = 12
118 Correct 8 ms 6896 KB Output is correct : V - N = 12
119 Correct 8 ms 6904 KB Output is correct : V - N = 12
120 Correct 8 ms 6928 KB Output is correct : V - N = 12
121 Correct 8 ms 6904 KB Output is correct : V - N = 12
122 Correct 8 ms 6640 KB Output is correct : V - N = 12
123 Correct 8 ms 6648 KB Output is correct : V - N = 12
124 Correct 8 ms 6640 KB Output is correct : V - N = 12
125 Correct 8 ms 6640 KB Output is correct : V - N = 12
126 Correct 8 ms 6792 KB Output is correct : V - N = 12
127 Correct 8 ms 6896 KB Output is correct : V - N = 12
128 Correct 8 ms 6640 KB Output is correct : V - N = 12
129 Correct 8 ms 6896 KB Output is correct : V - N = 12
130 Correct 8 ms 6896 KB Output is correct : V - N = 12
131 Correct 8 ms 6640 KB Output is correct : V - N = 12
132 Correct 8 ms 6640 KB Output is correct : V - N = 12
133 Correct 8 ms 6808 KB Output is correct : V - N = 12
134 Correct 8 ms 6848 KB Output is correct : V - N = 12
135 Correct 8 ms 6640 KB Output is correct : V - N = 12
136 Correct 8 ms 6736 KB Output is correct : V - N = 12
137 Correct 8 ms 6896 KB Output is correct : V - N = 12
138 Correct 8 ms 6896 KB Output is correct : V - N = 12
139 Correct 8 ms 6736 KB Output is correct : V - N = 12
140 Correct 8 ms 6736 KB Output is correct : V - N = 12
141 Correct 8 ms 6640 KB Output is correct : V - N = 12
142 Correct 8 ms 6896 KB Output is correct : V - N = 12
143 Correct 8 ms 6904 KB Output is correct : V - N = 12
144 Correct 8 ms 6896 KB Output is correct : V - N = 12
145 Correct 8 ms 6640 KB Output is correct : V - N = 12
146 Correct 8 ms 6896 KB Output is correct : V - N = 12
147 Correct 8 ms 6648 KB Output is correct : V - N = 12
148 Correct 13 ms 6896 KB Output is correct : V - N = 12
149 Correct 8 ms 6896 KB Output is correct : V - N = 12
150 Correct 8 ms 6640 KB Output is correct : V - N = 12
151 Correct 8 ms 6720 KB Output is correct : V - N = 12
152 Correct 9 ms 6744 KB Output is correct : V - N = 12
153 Correct 7 ms 6640 KB Output is correct : V - N = 12
154 Correct 9 ms 6896 KB Output is correct : V - N = 12
155 Correct 8 ms 6640 KB Output is correct : V - N = 12
156 Correct 8 ms 6896 KB Output is correct : V - N = 12
157 Correct 8 ms 6640 KB Output is correct : V - N = 12
158 Correct 8 ms 6896 KB Output is correct : V - N = 12
159 Correct 9 ms 6688 KB Output is correct : V - N = 12
160 Correct 8 ms 6896 KB Output is correct : V - N = 12
161 Correct 8 ms 6896 KB Output is correct : V - N = 12
162 Correct 8 ms 6640 KB Output is correct : V - N = 12
163 Correct 8 ms 6648 KB Output is correct : V - N = 12
164 Correct 8 ms 6680 KB Output is correct : V - N = 12
165 Correct 8 ms 6736 KB Output is correct : V - N = 12
166 Correct 8 ms 6896 KB Output is correct : V - N = 12
167 Correct 8 ms 6640 KB Output is correct : V - N = 12
168 Correct 8 ms 6904 KB Output is correct : V - N = 12
169 Correct 8 ms 7160 KB Output is correct : V - N = 12
170 Correct 8 ms 6760 KB Output is correct : V - N = 12
171 Correct 7 ms 6896 KB Output is correct : V - N = 0
172 Incorrect 5 ms 3320 KB Wrong Answer [6]
173 Halted 0 ms 0 KB -