답안 #407080

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
407080 2021-05-18T12:50:56 Z 79brue 항공 노선도 (JOI18_airline) C++14
0 / 100
849 ms 33472 KB
#include "Alicelib.h"
#include <bits/stdc++.h>

using namespace std;

namespace AliceLib{
    int n, m;
    int renum[1002];
    vector<int> link[1002];
    vector<pair<int, int> > resultingGraph;

    int counter[10];
    int oneHand = -1;

    void Alice(int N, int M, int A[], int B[]){
        n = N, m = M;
        for(int i=0; i<m; i++){
            link[A[i]].push_back(B[i]);
            link[B[i]].push_back(A[i]);

            resultingGraph.push_back(make_pair(A[i], B[i]));
        }

        for(int i=0; i<n; i++) for(int j=0; j<10; j++){
            if((i>>j)&1) counter[j]++;
        }
        for(int i=0; i<10; i++) if(counter[i] != 8) oneHand = i;
        if(oneHand == -1) exit(1);

        int rpnt = 0;
        for(int i=0; i<n; i++){
            while(__builtin_popcount(rpnt) >= 9) rpnt++;
            renum[i] = rpnt++;
        }

        /// Edge type A: 0 - 1 - ... - 9
        for(int i=0; i<10; i++) if((i+1)%10 != oneHand) resultingGraph.push_back(make_pair(n+i, n+(i+1)%10));

        /// Edge type B: Every other vertexes - (n+10)
        for(int i=0; i<n+10; i++){
            if(i!=n+oneHand) resultingGraph.push_back(make_pair(i, n+10));
        }

        /// Edge type C: n~n+9 - n+11
        for(int i=n; i<n+10; i++) resultingGraph.push_back(make_pair(i, n+11));

        /// Edge type D: 0~n-1 - n~n+9
        for(int i=0; i<n; i++){
            for(int j=0; j<10; j++){
                if((renum[i]>>j)&1) resultingGraph.push_back(make_pair(i, n+j));
            }
        }

        InitG(n+12, (int)resultingGraph.size());
        int edgeCnt = 0;
        for(auto p: resultingGraph){
            MakeG(edgeCnt++, p.first, p.second);
        }
    }
}

void Alice(int N, int M, int A[], int B[]){
    AliceLib::Alice(N, M, A, B);
}

#include <bits/stdc++.h>
#include "Boblib.h"

using namespace std;

namespace BobLib{
    int n, m;
    vector<int> link[1022];
    int deg[1022];
    int number[1022];
    int loc[1022];

    bool candidate[1022];

    int renum[1022];
    vector<pair<int, int> > edges;

    int counter[10];
    int oneHand;

    void Bob(int N, int M, int A[], int B[]){
        n = N - 12, m = M;
        for(int i=0; i<m; i++){
            link[A[i]].push_back(B[i]);
            link[B[i]].push_back(A[i]);
            deg[A[i]]++, deg[B[i]]++;
        }

        int rpnt = 0;
        for(int i=0; i<n; i++){
            while(__builtin_popcount(rpnt) >= 9) rpnt++;
            renum[rpnt++] = i;
        }

        for(int i=0; i<n; i++) for(int j=0; j<10; j++){
            if((i>>j)&1) counter[j]++;
        }
        for(int i=0; i<10; i++) if(counter[i] != 8) oneHand = i;

        for(int i=0; i<n+12; i++){
            if(deg[i] == n+9){
                loc[n+10] = i, number[i] = n+10;

                set<int> st;
                for(int j=0; j<n+12; j++) if(j!=i) st.insert(j);
                for(auto y: link[i]) st.erase(y);

                int pnt = *st.begin();
                if(deg[pnt] != 10) pnt = *st.rbegin();
                loc[n+11] = pnt, number[pnt] = n;

                pnt = *st.begin() + *st.rbegin() - pnt;
                loc[n+oneHand] = pnt, number[pnt] = n+oneHand;
            }
        }

        for(auto nxt: link[loc[n+11]]) candidate[nxt] = 1;
        int pnt = loc[n+oneHand];
        for(int i=n+(oneHand+1)%10; i != n+oneHand; i = (i==n+9 ? n : i+1)){
            for(auto nxt: link[pnt]){
                if(number[nxt] || !candidate[nxt]) continue;
                pnt = nxt;
                loc[i] = pnt, number[pnt] = i;
                break;
            }
        }

        for(int i=0; i<n+12; i++){
            if(number[i] >= n) continue;
            for(auto j: link[i]){
                if(number[j] < n || number[j] == n+10) continue;
                number[i] += 1 << (number[j] - n);
            }
            number[i] = renum[number[i]];
        }

        for(int i=0; i<n+12; i++){
            if(number[i] >= n) continue;
            for(auto j: link[i]){
                if(number[j] >= n || number[j] > number[i]) continue;
                edges.emplace_back(number[i], number[j]);
            }
        }

        InitMap(n, (int)edges.size());
        for(auto p: edges){
            MakeMap(p.first, p.second);
        }
    }
}

void Bob(int N, int M, int A[], int B[]){
    BobLib::Bob(N, M, A, B);
}

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 3 ms 4648 KB Output is correct
3 Correct 4 ms 4696 KB Output is correct
4 Correct 3 ms 4692 KB Output is correct
5 Correct 3 ms 4712 KB Output is correct
6 Correct 3 ms 4716 KB Output is correct
7 Correct 3 ms 4716 KB Output is correct
8 Correct 3 ms 4716 KB Output is correct
9 Correct 3 ms 4716 KB Output is correct
10 Correct 3 ms 4524 KB Output is correct
11 Correct 3 ms 4644 KB Output is correct
12 Correct 3 ms 4724 KB Output is correct
13 Correct 4 ms 4644 KB Output is correct
14 Correct 3 ms 4716 KB Output is correct
15 Correct 4 ms 4624 KB Output is correct
16 Correct 3 ms 4656 KB Output is correct
17 Correct 3 ms 4692 KB Output is correct
18 Correct 4 ms 4716 KB Output is correct
19 Correct 4 ms 4640 KB Output is correct
20 Correct 3 ms 4716 KB Output is correct
21 Correct 4 ms 4712 KB Output is correct
22 Correct 3 ms 4624 KB Output is correct
23 Correct 3 ms 4624 KB Output is correct
24 Correct 3 ms 4624 KB Output is correct
25 Correct 4 ms 4712 KB Output is correct
26 Correct 3 ms 4716 KB Output is correct
27 Correct 3 ms 4712 KB Output is correct
28 Correct 4 ms 4712 KB Output is correct
29 Correct 4 ms 4680 KB Output is correct
30 Correct 3 ms 4496 KB Output is correct
31 Correct 3 ms 4708 KB Output is correct
32 Correct 3 ms 4712 KB Output is correct
33 Correct 4 ms 4712 KB Output is correct
34 Correct 4 ms 4692 KB Output is correct
35 Correct 3 ms 4708 KB Output is correct
36 Correct 5 ms 4644 KB Output is correct
37 Correct 3 ms 4716 KB Output is correct
38 Correct 3 ms 4716 KB Output is correct
39 Correct 4 ms 4716 KB Output is correct
40 Correct 3 ms 4724 KB Output is correct
41 Correct 3 ms 4696 KB Output is correct
42 Correct 4 ms 4644 KB Output is correct
43 Correct 4 ms 4572 KB Output is correct
44 Correct 3 ms 4540 KB Output is correct
45 Correct 3 ms 4524 KB Output is correct
46 Correct 4 ms 4644 KB Output is correct
47 Correct 4 ms 4712 KB Output is correct
48 Correct 3 ms 4668 KB Output is correct
49 Correct 3 ms 4692 KB Output is correct
50 Correct 4 ms 4720 KB Output is correct
51 Incorrect 3 ms 4584 KB Wrong Answer [11]
52 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 3 ms 4648 KB Output is correct
3 Correct 4 ms 4696 KB Output is correct
4 Correct 3 ms 4692 KB Output is correct
5 Correct 3 ms 4712 KB Output is correct
6 Correct 3 ms 4716 KB Output is correct
7 Correct 3 ms 4716 KB Output is correct
8 Correct 3 ms 4716 KB Output is correct
9 Correct 3 ms 4716 KB Output is correct
10 Correct 3 ms 4524 KB Output is correct
11 Correct 3 ms 4644 KB Output is correct
12 Correct 3 ms 4724 KB Output is correct
13 Correct 4 ms 4644 KB Output is correct
14 Correct 3 ms 4716 KB Output is correct
15 Correct 4 ms 4624 KB Output is correct
16 Correct 3 ms 4656 KB Output is correct
17 Correct 3 ms 4692 KB Output is correct
18 Correct 4 ms 4716 KB Output is correct
19 Correct 4 ms 4640 KB Output is correct
20 Correct 3 ms 4716 KB Output is correct
21 Correct 4 ms 4712 KB Output is correct
22 Correct 3 ms 4624 KB Output is correct
23 Correct 3 ms 4624 KB Output is correct
24 Correct 3 ms 4624 KB Output is correct
25 Correct 4 ms 4712 KB Output is correct
26 Correct 3 ms 4716 KB Output is correct
27 Correct 3 ms 4712 KB Output is correct
28 Correct 4 ms 4712 KB Output is correct
29 Correct 4 ms 4680 KB Output is correct
30 Correct 3 ms 4496 KB Output is correct
31 Correct 3 ms 4708 KB Output is correct
32 Correct 3 ms 4712 KB Output is correct
33 Correct 4 ms 4712 KB Output is correct
34 Correct 4 ms 4692 KB Output is correct
35 Correct 3 ms 4708 KB Output is correct
36 Correct 5 ms 4644 KB Output is correct
37 Correct 3 ms 4716 KB Output is correct
38 Correct 3 ms 4716 KB Output is correct
39 Correct 4 ms 4716 KB Output is correct
40 Correct 3 ms 4724 KB Output is correct
41 Correct 3 ms 4696 KB Output is correct
42 Correct 4 ms 4644 KB Output is correct
43 Correct 4 ms 4572 KB Output is correct
44 Correct 3 ms 4540 KB Output is correct
45 Correct 3 ms 4524 KB Output is correct
46 Correct 4 ms 4644 KB Output is correct
47 Correct 4 ms 4712 KB Output is correct
48 Correct 3 ms 4668 KB Output is correct
49 Correct 3 ms 4692 KB Output is correct
50 Correct 4 ms 4720 KB Output is correct
51 Incorrect 3 ms 4584 KB Wrong Answer [11]
52 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 815 ms 33464 KB Output is correct : V - N = 12
2 Correct 585 ms 30316 KB Output is correct : V - N = 12
3 Correct 223 ms 16112 KB Output is correct : V - N = 12
4 Correct 11 ms 5408 KB Output is correct : V - N = 12
5 Correct 158 ms 11120 KB Output is correct : V - N = 12
6 Correct 535 ms 28208 KB Output is correct : V - N = 12
7 Correct 770 ms 33348 KB Output is correct : V - N = 12
8 Correct 603 ms 31868 KB Output is correct : V - N = 12
9 Correct 296 ms 18460 KB Output is correct : V - N = 12
10 Correct 40 ms 6584 KB Output is correct : V - N = 12
11 Correct 70 ms 8056 KB Output is correct : V - N = 12
12 Correct 362 ms 21144 KB Output is correct : V - N = 12
13 Correct 678 ms 32480 KB Output is correct : V - N = 12
14 Correct 770 ms 32836 KB Output is correct : V - N = 12
15 Correct 516 ms 27092 KB Output is correct : V - N = 12
16 Correct 118 ms 9148 KB Output is correct : V - N = 12
17 Correct 25 ms 5980 KB Output is correct : V - N = 12
18 Correct 263 ms 17340 KB Output is correct : V - N = 12
19 Correct 555 ms 30916 KB Output is correct : V - N = 12
20 Correct 748 ms 33408 KB Output is correct : V - N = 12
21 Correct 163 ms 13404 KB Output is correct : V - N = 12
22 Correct 193 ms 11488 KB Output is correct : V - N = 12
23 Correct 69 ms 7884 KB Output is correct : V - N = 12
24 Correct 6 ms 4880 KB Output is correct : V - N = 12
25 Correct 37 ms 6612 KB Output is correct : V - N = 12
26 Correct 146 ms 10952 KB Output is correct : V - N = 12
27 Correct 197 ms 12328 KB Output is correct : V - N = 12
28 Correct 157 ms 11956 KB Output is correct : V - N = 12
29 Correct 80 ms 8436 KB Output is correct : V - N = 12
30 Correct 11 ms 5392 KB Output is correct : V - N = 12
31 Correct 12 ms 5052 KB Output is correct : V - N = 12
32 Correct 11 ms 5012 KB Output is correct : V - N = 12
33 Correct 11 ms 5064 KB Output is correct : V - N = 12
34 Correct 10 ms 5024 KB Output is correct : V - N = 12
35 Correct 10 ms 5008 KB Output is correct : V - N = 12
36 Correct 713 ms 33312 KB Output is correct : V - N = 12
37 Correct 772 ms 33372 KB Output is correct : V - N = 12
38 Correct 744 ms 33396 KB Output is correct : V - N = 12
39 Correct 769 ms 33260 KB Output is correct : V - N = 12
40 Correct 761 ms 33472 KB Output is correct : V - N = 12
41 Correct 157 ms 10872 KB Output is correct : V - N = 12
42 Correct 130 ms 9508 KB Output is correct : V - N = 12
43 Correct 137 ms 10620 KB Output is correct : V - N = 12
44 Correct 10 ms 5156 KB Output is correct : V - N = 12
45 Correct 67 ms 8056 KB Output is correct : V - N = 12
46 Correct 280 ms 16664 KB Output is correct : V - N = 12
47 Correct 117 ms 11104 KB Output is correct : V - N = 12
48 Correct 366 ms 18500 KB Output is correct : V - N = 12
49 Correct 69 ms 8068 KB Output is correct : V - N = 12
50 Correct 20 ms 5964 KB Output is correct : V - N = 12
51 Correct 558 ms 30068 KB Output is correct : V - N = 12
52 Correct 13 ms 5264 KB Output is correct : V - N = 12
53 Correct 534 ms 28120 KB Output is correct : V - N = 12
54 Correct 602 ms 31492 KB Output is correct : V - N = 12
55 Correct 51 ms 6600 KB Output is correct : V - N = 12
56 Correct 422 ms 20440 KB Output is correct : V - N = 12
57 Correct 803 ms 32468 KB Output is correct : V - N = 12
58 Correct 96 ms 8928 KB Output is correct : V - N = 12
59 Correct 348 ms 17348 KB Output is correct : V - N = 12
60 Correct 849 ms 32872 KB Output is correct : V - N = 12
61 Correct 4 ms 4844 KB Output is correct : V - N = 12
62 Correct 4 ms 4784 KB Output is correct : V - N = 12
63 Correct 4 ms 4716 KB Output is correct : V - N = 12
64 Correct 3 ms 4748 KB Output is correct : V - N = 12
65 Correct 3 ms 4724 KB Output is correct : V - N = 12
66 Correct 3 ms 4828 KB Output is correct : V - N = 12
67 Correct 4 ms 4840 KB Output is correct : V - N = 12
68 Correct 4 ms 4840 KB Output is correct : V - N = 12
69 Correct 4 ms 4716 KB Output is correct : V - N = 12
70 Correct 3 ms 4716 KB Output is correct : V - N = 12
71 Correct 3 ms 4716 KB Output is correct : V - N = 12
72 Correct 3 ms 4720 KB Output is correct : V - N = 12
73 Correct 4 ms 4724 KB Output is correct : V - N = 12
74 Correct 4 ms 4784 KB Output is correct : V - N = 12
75 Correct 3 ms 4844 KB Output is correct : V - N = 12
76 Correct 4 ms 4700 KB Output is correct : V - N = 12
77 Correct 3 ms 4640 KB Output is correct : V - N = 12
78 Correct 3 ms 4644 KB Output is correct : V - N = 12
79 Correct 4 ms 4824 KB Output is correct : V - N = 12
80 Correct 4 ms 4820 KB Output is correct : V - N = 12
81 Correct 4 ms 4840 KB Output is correct : V - N = 12
82 Correct 4 ms 4716 KB Output is correct : V - N = 12
83 Correct 3 ms 4716 KB Output is correct : V - N = 12
84 Correct 4 ms 4692 KB Output is correct : V - N = 12
85 Correct 3 ms 4716 KB Output is correct : V - N = 12
86 Correct 4 ms 4696 KB Output is correct : V - N = 12
87 Correct 4 ms 4824 KB Output is correct : V - N = 12
88 Correct 3 ms 4708 KB Output is correct : V - N = 12
89 Correct 3 ms 4724 KB Output is correct : V - N = 12
90 Correct 3 ms 4716 KB Output is correct : V - N = 12
91 Correct 3 ms 4568 KB Output is correct : V - N = 12
92 Correct 3 ms 4712 KB Output is correct : V - N = 12
93 Correct 3 ms 4712 KB Output is correct : V - N = 12
94 Correct 3 ms 4712 KB Output is correct : V - N = 12
95 Correct 3 ms 4712 KB Output is correct : V - N = 12
96 Correct 4 ms 4844 KB Output is correct : V - N = 12
97 Correct 5 ms 4844 KB Output is correct : V - N = 12
98 Correct 5 ms 4764 KB Output is correct : V - N = 12
99 Correct 4 ms 4768 KB Output is correct : V - N = 12
100 Correct 4 ms 4796 KB Output is correct : V - N = 12
101 Correct 4 ms 4716 KB Output is correct : V - N = 12
102 Correct 4 ms 4696 KB Output is correct : V - N = 12
103 Correct 4 ms 4644 KB Output is correct : V - N = 12
104 Correct 3 ms 4712 KB Output is correct : V - N = 12
105 Correct 3 ms 4716 KB Output is correct : V - N = 12
106 Correct 3 ms 4696 KB Output is correct : V - N = 12
107 Correct 3 ms 4716 KB Output is correct : V - N = 12
108 Correct 3 ms 4820 KB Output is correct : V - N = 12
109 Correct 3 ms 4712 KB Output is correct : V - N = 12
110 Correct 4 ms 4708 KB Output is correct : V - N = 12
111 Correct 4 ms 4812 KB Output is correct : V - N = 12
112 Correct 3 ms 4716 KB Output is correct : V - N = 12
113 Correct 3 ms 4624 KB Output is correct : V - N = 12
114 Correct 5 ms 4728 KB Output is correct : V - N = 12
115 Correct 3 ms 4696 KB Output is correct : V - N = 12
116 Correct 4 ms 4716 KB Output is correct : V - N = 12
117 Correct 4 ms 4712 KB Output is correct : V - N = 12
118 Correct 3 ms 4644 KB Output is correct : V - N = 12
119 Correct 3 ms 4716 KB Output is correct : V - N = 12
120 Correct 4 ms 4644 KB Output is correct : V - N = 12
121 Correct 3 ms 4716 KB Output is correct : V - N = 12
122 Correct 3 ms 4668 KB Output is correct : V - N = 12
123 Correct 3 ms 4708 KB Output is correct : V - N = 12
124 Correct 3 ms 4584 KB Output is correct : V - N = 12
125 Correct 4 ms 4644 KB Output is correct : V - N = 12
126 Correct 3 ms 4716 KB Output is correct : V - N = 12
127 Correct 4 ms 4696 KB Output is correct : V - N = 12
128 Correct 3 ms 4716 KB Output is correct : V - N = 12
129 Correct 3 ms 4716 KB Output is correct : V - N = 12
130 Correct 3 ms 4748 KB Output is correct : V - N = 12
131 Correct 4 ms 4652 KB Output is correct : V - N = 12
132 Correct 3 ms 4716 KB Output is correct : V - N = 12
133 Correct 3 ms 4716 KB Output is correct : V - N = 12
134 Correct 3 ms 4652 KB Output is correct : V - N = 12
135 Correct 3 ms 4724 KB Output is correct : V - N = 12
136 Correct 3 ms 4716 KB Output is correct : V - N = 12
137 Correct 3 ms 4696 KB Output is correct : V - N = 12
138 Correct 3 ms 4624 KB Output is correct : V - N = 12
139 Correct 3 ms 4716 KB Output is correct : V - N = 12
140 Correct 3 ms 4668 KB Output is correct : V - N = 12
141 Correct 3 ms 4644 KB Output is correct : V - N = 12
142 Correct 3 ms 4656 KB Output is correct : V - N = 12
143 Correct 3 ms 4728 KB Output is correct : V - N = 12
144 Correct 4 ms 4564 KB Output is correct : V - N = 12
145 Correct 3 ms 4716 KB Output is correct : V - N = 12
146 Correct 3 ms 4716 KB Output is correct : V - N = 12
147 Correct 3 ms 4708 KB Output is correct : V - N = 12
148 Correct 3 ms 4716 KB Output is correct : V - N = 12
149 Correct 4 ms 4640 KB Output is correct : V - N = 12
150 Correct 3 ms 4712 KB Output is correct : V - N = 12
151 Correct 3 ms 4708 KB Output is correct : V - N = 12
152 Correct 3 ms 4656 KB Output is correct : V - N = 12
153 Correct 3 ms 4712 KB Output is correct : V - N = 12
154 Correct 3 ms 4584 KB Output is correct : V - N = 12
155 Correct 3 ms 4692 KB Output is correct : V - N = 12
156 Correct 3 ms 4716 KB Output is correct : V - N = 12
157 Correct 3 ms 4724 KB Output is correct : V - N = 12
158 Correct 3 ms 4644 KB Output is correct : V - N = 12
159 Correct 4 ms 4696 KB Output is correct : V - N = 12
160 Correct 3 ms 4716 KB Output is correct : V - N = 12
161 Correct 4 ms 4716 KB Output is correct : V - N = 12
162 Correct 3 ms 4716 KB Output is correct : V - N = 12
163 Correct 3 ms 4724 KB Output is correct : V - N = 12
164 Correct 3 ms 4584 KB Output is correct : V - N = 12
165 Correct 3 ms 4712 KB Output is correct : V - N = 12
166 Correct 3 ms 4648 KB Output is correct : V - N = 12
167 Correct 3 ms 4624 KB Output is correct : V - N = 12
168 Correct 3 ms 4716 KB Output is correct : V - N = 12
169 Correct 4 ms 4644 KB Output is correct : V - N = 12
170 Correct 3 ms 4644 KB Output is correct : V - N = 12
171 Incorrect 3 ms 4624 KB Wrong Answer [11]
172 Halted 0 ms 0 KB -