답안 #407067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
407067 2021-05-18T12:31:46 Z 79brue 항공 노선도 (JOI18_airline) C++14
0 / 100
889 ms 33548 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;

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

        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<9; i++) resultingGraph.push_back(make_pair(n+i, n+i+1));

        /// Edge type B: Every other vertexes - (n+10)
        for(int i=0; i<n+10; i++){
            if(i!=n) 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;

    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+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] = pnt, number[pnt] = n;
            }
        }

        for(auto nxt: link[loc[n+11]]) candidate[nxt] = 1;
        int pnt = loc[n];
        for(int i=n+1; i<n+10; i++){
            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 4716 KB Output is correct
2 Correct 3 ms 4628 KB Output is correct
3 Correct 3 ms 4664 KB Output is correct
4 Correct 3 ms 4692 KB Output is correct
5 Correct 3 ms 4696 KB Output is correct
6 Correct 3 ms 4724 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 4624 KB Output is correct
11 Correct 3 ms 4628 KB Output is correct
12 Correct 3 ms 4696 KB Output is correct
13 Correct 3 ms 4624 KB Output is correct
14 Correct 3 ms 4716 KB Output is correct
15 Correct 4 ms 4712 KB Output is correct
16 Correct 3 ms 4716 KB Output is correct
17 Correct 3 ms 4716 KB Output is correct
18 Correct 3 ms 4716 KB Output is correct
19 Correct 3 ms 4716 KB Output is correct
20 Correct 3 ms 4644 KB Output is correct
21 Correct 3 ms 4724 KB Output is correct
22 Correct 4 ms 4716 KB Output is correct
23 Correct 3 ms 4712 KB Output is correct
24 Correct 3 ms 4708 KB Output is correct
25 Correct 3 ms 4716 KB Output is correct
26 Correct 3 ms 4724 KB Output is correct
27 Correct 3 ms 4628 KB Output is correct
28 Correct 4 ms 4716 KB Output is correct
29 Correct 4 ms 4624 KB Output is correct
30 Correct 4 ms 4584 KB Output is correct
31 Correct 3 ms 4580 KB Output is correct
32 Correct 3 ms 4840 KB Output is correct
33 Correct 3 ms 4720 KB Output is correct
34 Correct 3 ms 4644 KB Output is correct
35 Correct 3 ms 4528 KB Output is correct
36 Correct 3 ms 4696 KB Output is correct
37 Correct 4 ms 4716 KB Output is correct
38 Correct 4 ms 4704 KB Output is correct
39 Correct 3 ms 4652 KB Output is correct
40 Correct 3 ms 4716 KB Output is correct
41 Correct 3 ms 4716 KB Output is correct
42 Correct 3 ms 4716 KB Output is correct
43 Correct 3 ms 4644 KB Output is correct
44 Correct 4 ms 4564 KB Output is correct
45 Correct 3 ms 4712 KB Output is correct
46 Correct 3 ms 4676 KB Output is correct
47 Correct 4 ms 4712 KB Output is correct
48 Correct 3 ms 4716 KB Output is correct
49 Correct 3 ms 4664 KB Output is correct
50 Correct 3 ms 4584 KB Output is correct
51 Incorrect 3 ms 4724 KB Wrong Answer [11]
52 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4716 KB Output is correct
2 Correct 3 ms 4628 KB Output is correct
3 Correct 3 ms 4664 KB Output is correct
4 Correct 3 ms 4692 KB Output is correct
5 Correct 3 ms 4696 KB Output is correct
6 Correct 3 ms 4724 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 4624 KB Output is correct
11 Correct 3 ms 4628 KB Output is correct
12 Correct 3 ms 4696 KB Output is correct
13 Correct 3 ms 4624 KB Output is correct
14 Correct 3 ms 4716 KB Output is correct
15 Correct 4 ms 4712 KB Output is correct
16 Correct 3 ms 4716 KB Output is correct
17 Correct 3 ms 4716 KB Output is correct
18 Correct 3 ms 4716 KB Output is correct
19 Correct 3 ms 4716 KB Output is correct
20 Correct 3 ms 4644 KB Output is correct
21 Correct 3 ms 4724 KB Output is correct
22 Correct 4 ms 4716 KB Output is correct
23 Correct 3 ms 4712 KB Output is correct
24 Correct 3 ms 4708 KB Output is correct
25 Correct 3 ms 4716 KB Output is correct
26 Correct 3 ms 4724 KB Output is correct
27 Correct 3 ms 4628 KB Output is correct
28 Correct 4 ms 4716 KB Output is correct
29 Correct 4 ms 4624 KB Output is correct
30 Correct 4 ms 4584 KB Output is correct
31 Correct 3 ms 4580 KB Output is correct
32 Correct 3 ms 4840 KB Output is correct
33 Correct 3 ms 4720 KB Output is correct
34 Correct 3 ms 4644 KB Output is correct
35 Correct 3 ms 4528 KB Output is correct
36 Correct 3 ms 4696 KB Output is correct
37 Correct 4 ms 4716 KB Output is correct
38 Correct 4 ms 4704 KB Output is correct
39 Correct 3 ms 4652 KB Output is correct
40 Correct 3 ms 4716 KB Output is correct
41 Correct 3 ms 4716 KB Output is correct
42 Correct 3 ms 4716 KB Output is correct
43 Correct 3 ms 4644 KB Output is correct
44 Correct 4 ms 4564 KB Output is correct
45 Correct 3 ms 4712 KB Output is correct
46 Correct 3 ms 4676 KB Output is correct
47 Correct 4 ms 4712 KB Output is correct
48 Correct 3 ms 4716 KB Output is correct
49 Correct 3 ms 4664 KB Output is correct
50 Correct 3 ms 4584 KB Output is correct
51 Incorrect 3 ms 4724 KB Wrong Answer [11]
52 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 836 ms 33404 KB Output is correct : V - N = 12
2 Correct 542 ms 30208 KB Output is correct : V - N = 12
3 Correct 229 ms 16192 KB Output is correct : V - N = 12
4 Correct 13 ms 5264 KB Output is correct : V - N = 12
5 Correct 152 ms 11184 KB Output is correct : V - N = 12
6 Correct 628 ms 28180 KB Output is correct : V - N = 12
7 Correct 686 ms 33468 KB Output is correct : V - N = 12
8 Correct 614 ms 31776 KB Output is correct : V - N = 12
9 Correct 315 ms 18352 KB Output is correct : V - N = 12
10 Correct 52 ms 6652 KB Output is correct : V - N = 12
11 Correct 81 ms 7980 KB Output is correct : V - N = 12
12 Correct 392 ms 21384 KB Output is correct : V - N = 12
13 Correct 723 ms 32424 KB Output is correct : V - N = 12
14 Correct 632 ms 33080 KB Output is correct : V - N = 12
15 Correct 424 ms 26980 KB Output is correct : V - N = 12
16 Correct 123 ms 9100 KB Output is correct : V - N = 12
17 Correct 20 ms 5964 KB Output is correct : V - N = 12
18 Correct 267 ms 17364 KB Output is correct : V - N = 12
19 Correct 693 ms 31132 KB Output is correct : V - N = 12
20 Correct 889 ms 33548 KB Output is correct : V - N = 12
21 Correct 170 ms 13524 KB Output is correct : V - N = 12
22 Correct 175 ms 11556 KB Output is correct : V - N = 12
23 Correct 52 ms 7928 KB Output is correct : V - N = 12
24 Correct 7 ms 4784 KB Output is correct : V - N = 12
25 Correct 47 ms 6568 KB Output is correct : V - N = 12
26 Correct 108 ms 10980 KB Output is correct : V - N = 12
27 Correct 231 ms 12440 KB Output is correct : V - N = 12
28 Correct 160 ms 11976 KB Output is correct : V - N = 12
29 Correct 88 ms 8488 KB Output is correct : V - N = 12
30 Correct 12 ms 5492 KB Output is correct : V - N = 12
31 Correct 12 ms 5008 KB Output is correct : V - N = 12
32 Correct 10 ms 5076 KB Output is correct : V - N = 12
33 Correct 10 ms 5096 KB Output is correct : V - N = 12
34 Correct 10 ms 5108 KB Output is correct : V - N = 12
35 Correct 9 ms 5024 KB Output is correct : V - N = 12
36 Correct 808 ms 33376 KB Output is correct : V - N = 12
37 Correct 758 ms 33468 KB Output is correct : V - N = 12
38 Correct 788 ms 33436 KB Output is correct : V - N = 12
39 Correct 709 ms 33460 KB Output is correct : V - N = 12
40 Correct 679 ms 33368 KB Output is correct : V - N = 12
41 Correct 154 ms 10976 KB Output is correct : V - N = 12
42 Correct 108 ms 9488 KB Output is correct : V - N = 12
43 Correct 142 ms 10592 KB Output is correct : V - N = 12
44 Correct 12 ms 5024 KB Output is correct : V - N = 12
45 Correct 83 ms 8052 KB Output is correct : V - N = 12
46 Correct 294 ms 16676 KB Output is correct : V - N = 12
47 Correct 159 ms 10796 KB Output is correct : V - N = 12
48 Correct 455 ms 18472 KB Output is correct : V - N = 12
49 Correct 77 ms 7836 KB Output is correct : V - N = 12
50 Correct 25 ms 5888 KB Output is correct : V - N = 12
51 Correct 670 ms 30144 KB Output is correct : V - N = 12
52 Correct 12 ms 5264 KB Output is correct : V - N = 12
53 Correct 472 ms 27948 KB Output is correct : V - N = 12
54 Correct 570 ms 31408 KB Output is correct : V - N = 12
55 Correct 36 ms 6656 KB Output is correct : V - N = 12
56 Correct 376 ms 20380 KB Output is correct : V - N = 12
57 Correct 805 ms 32628 KB Output is correct : V - N = 12
58 Correct 115 ms 8920 KB Output is correct : V - N = 12
59 Correct 273 ms 17100 KB Output is correct : V - N = 12
60 Correct 825 ms 32796 KB Output is correct : V - N = 12
61 Correct 5 ms 4848 KB Output is correct : V - N = 12
62 Correct 5 ms 4844 KB Output is correct : V - N = 12
63 Correct 3 ms 4692 KB Output is correct : V - N = 12
64 Correct 3 ms 4624 KB Output is correct : V - N = 12
65 Correct 3 ms 4796 KB Output is correct : V - N = 12
66 Correct 5 ms 4824 KB Output is correct : V - N = 12
67 Correct 5 ms 4824 KB Output is correct : V - N = 12
68 Correct 4 ms 4844 KB Output is correct : V - N = 12
69 Correct 4 ms 4644 KB Output is correct : V - N = 12
70 Correct 3 ms 4644 KB Output is correct : V - N = 12
71 Correct 3 ms 4696 KB Output is correct : V - N = 12
72 Correct 5 ms 4716 KB Output is correct : V - N = 12
73 Correct 4 ms 4836 KB Output is correct : V - N = 12
74 Correct 4 ms 4844 KB Output is correct : V - N = 12
75 Correct 5 ms 4716 KB Output is correct : V - N = 12
76 Correct 3 ms 4644 KB Output is correct : V - N = 12
77 Correct 4 ms 4644 KB Output is correct : V - N = 12
78 Correct 4 ms 4716 KB Output is correct : V - N = 12
79 Correct 4 ms 4844 KB Output is correct : V - N = 12
80 Correct 4 ms 4780 KB Output is correct : V - N = 12
81 Correct 4 ms 4844 KB Output is correct : V - N = 12
82 Correct 4 ms 4708 KB Output is correct : V - N = 12
83 Correct 4 ms 4716 KB Output is correct : V - N = 12
84 Correct 4 ms 4716 KB Output is correct : V - N = 12
85 Correct 3 ms 4716 KB Output is correct : V - N = 12
86 Correct 4 ms 4844 KB Output is correct : V - N = 12
87 Correct 4 ms 4824 KB Output is correct : V - N = 12
88 Correct 5 ms 4844 KB Output is correct : V - N = 12
89 Correct 4 ms 4716 KB Output is correct : V - N = 12
90 Correct 3 ms 4716 KB Output is correct : V - N = 12
91 Correct 3 ms 4712 KB Output is correct : V - N = 12
92 Correct 4 ms 4712 KB Output is correct : V - N = 12
93 Correct 3 ms 4692 KB Output is correct : V - N = 12
94 Correct 3 ms 4624 KB Output is correct : V - N = 12
95 Correct 3 ms 4644 KB Output is correct : V - N = 12
96 Correct 4 ms 4848 KB Output is correct : V - N = 12
97 Correct 4 ms 4820 KB Output is correct : V - N = 12
98 Correct 4 ms 4824 KB Output is correct : V - N = 12
99 Correct 5 ms 4772 KB Output is correct : V - N = 12
100 Correct 4 ms 4784 KB Output is correct : V - N = 12
101 Correct 4 ms 4624 KB Output is correct : V - N = 12
102 Correct 5 ms 4716 KB Output is correct : V - N = 12
103 Correct 3 ms 4696 KB Output is correct : V - N = 12
104 Correct 3 ms 4712 KB Output is correct : V - N = 12
105 Correct 3 ms 4720 KB Output is correct : V - N = 12
106 Correct 3 ms 4716 KB Output is correct : V - N = 12
107 Correct 5 ms 4844 KB Output is correct : V - N = 12
108 Correct 4 ms 4716 KB Output is correct : V - N = 12
109 Correct 3 ms 4712 KB Output is correct : V - N = 12
110 Correct 5 ms 4716 KB Output is correct : V - N = 12
111 Correct 4 ms 4752 KB Output is correct : V - N = 12
112 Correct 3 ms 4716 KB Output is correct : V - N = 12
113 Correct 5 ms 4692 KB Output is correct : V - N = 12
114 Correct 4 ms 4644 KB Output is correct : V - N = 12
115 Correct 3 ms 4716 KB Output is correct : V - N = 12
116 Correct 4 ms 4716 KB Output is correct : V - N = 12
117 Correct 4 ms 4836 KB Output is correct : V - N = 12
118 Correct 3 ms 4716 KB Output is correct : V - N = 12
119 Correct 4 ms 4708 KB Output is correct : V - N = 12
120 Correct 3 ms 4708 KB Output is correct : V - N = 12
121 Correct 3 ms 4692 KB Output is correct : V - N = 12
122 Correct 4 ms 4716 KB Output is correct : V - N = 12
123 Correct 3 ms 4624 KB Output is correct : V - N = 12
124 Correct 3 ms 4644 KB Output is correct : V - N = 12
125 Correct 3 ms 4712 KB Output is correct : V - N = 12
126 Correct 3 ms 4696 KB Output is correct : V - N = 12
127 Correct 4 ms 4624 KB Output is correct : V - N = 12
128 Correct 4 ms 4716 KB Output is correct : V - N = 12
129 Correct 4 ms 4716 KB Output is correct : V - N = 12
130 Correct 3 ms 4584 KB Output is correct : V - N = 12
131 Correct 3 ms 4716 KB Output is correct : V - N = 12
132 Correct 4 ms 4716 KB Output is correct : V - N = 12
133 Correct 4 ms 4716 KB Output is correct : V - N = 12
134 Correct 3 ms 4716 KB Output is correct : V - N = 12
135 Correct 3 ms 4728 KB Output is correct : V - N = 12
136 Correct 3 ms 4716 KB Output is correct : V - N = 12
137 Correct 3 ms 4724 KB Output is correct : V - N = 12
138 Correct 3 ms 4720 KB Output is correct : V - N = 12
139 Correct 3 ms 4712 KB Output is correct : V - N = 12
140 Correct 4 ms 4656 KB Output is correct : V - N = 12
141 Correct 3 ms 4724 KB Output is correct : V - N = 12
142 Correct 3 ms 4656 KB Output is correct : V - N = 12
143 Correct 3 ms 4716 KB Output is correct : V - N = 12
144 Correct 3 ms 4644 KB Output is correct : V - N = 12
145 Correct 3 ms 4716 KB Output is correct : V - N = 12
146 Correct 3 ms 4692 KB Output is correct : V - N = 12
147 Correct 3 ms 4716 KB Output is correct : V - N = 12
148 Correct 3 ms 4664 KB Output is correct : V - N = 12
149 Correct 3 ms 4716 KB Output is correct : V - N = 12
150 Correct 3 ms 4668 KB Output is correct : V - N = 12
151 Correct 3 ms 4512 KB Output is correct : V - N = 12
152 Correct 3 ms 4712 KB Output is correct : V - N = 12
153 Correct 5 ms 4556 KB Output is correct : V - N = 12
154 Correct 3 ms 4712 KB Output is correct : V - N = 12
155 Correct 4 ms 4712 KB Output is correct : V - N = 12
156 Correct 4 ms 4696 KB Output is correct : V - N = 12
157 Correct 3 ms 4640 KB Output is correct : V - N = 12
158 Correct 3 ms 4712 KB Output is correct : V - N = 12
159 Correct 4 ms 4624 KB Output is correct : V - N = 12
160 Correct 3 ms 4652 KB Output is correct : V - N = 12
161 Correct 4 ms 4716 KB Output is correct : V - N = 12
162 Correct 3 ms 4696 KB Output is correct : V - N = 12
163 Correct 4 ms 4700 KB Output is correct : V - N = 12
164 Correct 3 ms 4712 KB Output is correct : V - N = 12
165 Correct 4 ms 4576 KB Output is correct : V - N = 12
166 Correct 3 ms 4644 KB Output is correct : V - N = 12
167 Correct 3 ms 4720 KB Output is correct : V - N = 12
168 Correct 3 ms 4696 KB Output is correct : V - N = 12
169 Correct 3 ms 4716 KB Output is correct : V - N = 12
170 Correct 4 ms 4624 KB Output is correct : V - N = 12
171 Incorrect 3 ms 4712 KB Wrong Answer [11]
172 Halted 0 ms 0 KB -