Submission #407092

# Submission time Handle Problem Language Result Execution time Memory
407092 2021-05-18T13:05:45 Z 79brue Airline Route Map (JOI18_airline) C++14
0 / 100
867 ms 33776 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]++;
        }

        if(n < 500) oneHand = 9;
        else oneHand = 0;

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

        if(n < 500) oneHand = 9;
        else oneHand = 0;

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4660 KB Output is correct
2 Correct 4 ms 4716 KB Output is correct
3 Correct 3 ms 4716 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 4696 KB Output is correct
7 Correct 3 ms 4716 KB Output is correct
8 Correct 3 ms 4640 KB Output is correct
9 Correct 3 ms 4716 KB Output is correct
10 Correct 3 ms 4712 KB Output is correct
11 Correct 3 ms 4716 KB Output is correct
12 Correct 3 ms 4712 KB Output is correct
13 Correct 3 ms 4720 KB Output is correct
14 Correct 3 ms 4728 KB Output is correct
15 Correct 4 ms 4640 KB Output is correct
16 Correct 4 ms 4716 KB Output is correct
17 Correct 3 ms 4668 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 4716 KB Output is correct
21 Correct 3 ms 4696 KB Output is correct
22 Correct 3 ms 4696 KB Output is correct
23 Correct 3 ms 4696 KB Output is correct
24 Correct 3 ms 4720 KB Output is correct
25 Correct 3 ms 4716 KB Output is correct
26 Correct 4 ms 4724 KB Output is correct
27 Correct 3 ms 4720 KB Output is correct
28 Correct 3 ms 4696 KB Output is correct
29 Correct 3 ms 4716 KB Output is correct
30 Correct 3 ms 4588 KB Output is correct
31 Correct 3 ms 4624 KB Output is correct
32 Correct 4 ms 4516 KB Output is correct
33 Correct 3 ms 4712 KB Output is correct
34 Correct 3 ms 4644 KB Output is correct
35 Correct 4 ms 4644 KB Output is correct
36 Correct 3 ms 4708 KB Output is correct
37 Correct 3 ms 4696 KB Output is correct
38 Correct 3 ms 4716 KB Output is correct
39 Correct 3 ms 4656 KB Output is correct
40 Correct 3 ms 4716 KB Output is correct
41 Correct 3 ms 4676 KB Output is correct
42 Correct 4 ms 4720 KB Output is correct
43 Correct 3 ms 4716 KB Output is correct
44 Correct 3 ms 4644 KB Output is correct
45 Correct 3 ms 4716 KB Output is correct
46 Correct 3 ms 4712 KB Output is correct
47 Correct 3 ms 4696 KB Output is correct
48 Correct 3 ms 4788 KB Output is correct
49 Correct 3 ms 4644 KB Output is correct
50 Correct 3 ms 4580 KB Output is correct
51 Incorrect 3 ms 4692 KB Wrong Answer [11]
52 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4660 KB Output is correct
2 Correct 4 ms 4716 KB Output is correct
3 Correct 3 ms 4716 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 4696 KB Output is correct
7 Correct 3 ms 4716 KB Output is correct
8 Correct 3 ms 4640 KB Output is correct
9 Correct 3 ms 4716 KB Output is correct
10 Correct 3 ms 4712 KB Output is correct
11 Correct 3 ms 4716 KB Output is correct
12 Correct 3 ms 4712 KB Output is correct
13 Correct 3 ms 4720 KB Output is correct
14 Correct 3 ms 4728 KB Output is correct
15 Correct 4 ms 4640 KB Output is correct
16 Correct 4 ms 4716 KB Output is correct
17 Correct 3 ms 4668 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 4716 KB Output is correct
21 Correct 3 ms 4696 KB Output is correct
22 Correct 3 ms 4696 KB Output is correct
23 Correct 3 ms 4696 KB Output is correct
24 Correct 3 ms 4720 KB Output is correct
25 Correct 3 ms 4716 KB Output is correct
26 Correct 4 ms 4724 KB Output is correct
27 Correct 3 ms 4720 KB Output is correct
28 Correct 3 ms 4696 KB Output is correct
29 Correct 3 ms 4716 KB Output is correct
30 Correct 3 ms 4588 KB Output is correct
31 Correct 3 ms 4624 KB Output is correct
32 Correct 4 ms 4516 KB Output is correct
33 Correct 3 ms 4712 KB Output is correct
34 Correct 3 ms 4644 KB Output is correct
35 Correct 4 ms 4644 KB Output is correct
36 Correct 3 ms 4708 KB Output is correct
37 Correct 3 ms 4696 KB Output is correct
38 Correct 3 ms 4716 KB Output is correct
39 Correct 3 ms 4656 KB Output is correct
40 Correct 3 ms 4716 KB Output is correct
41 Correct 3 ms 4676 KB Output is correct
42 Correct 4 ms 4720 KB Output is correct
43 Correct 3 ms 4716 KB Output is correct
44 Correct 3 ms 4644 KB Output is correct
45 Correct 3 ms 4716 KB Output is correct
46 Correct 3 ms 4712 KB Output is correct
47 Correct 3 ms 4696 KB Output is correct
48 Correct 3 ms 4788 KB Output is correct
49 Correct 3 ms 4644 KB Output is correct
50 Correct 3 ms 4580 KB Output is correct
51 Incorrect 3 ms 4692 KB Wrong Answer [11]
52 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 643 ms 33392 KB Output is correct : V - N = 12
2 Correct 593 ms 30168 KB Output is correct : V - N = 12
3 Correct 255 ms 16316 KB Output is correct : V - N = 12
4 Correct 13 ms 5352 KB Output is correct : V - N = 12
5 Correct 168 ms 11056 KB Output is correct : V - N = 12
6 Correct 427 ms 28212 KB Output is correct : V - N = 12
7 Correct 735 ms 33608 KB Output is correct : V - N = 12
8 Correct 751 ms 31916 KB Output is correct : V - N = 12
9 Correct 310 ms 18368 KB Output is correct : V - N = 12
10 Correct 43 ms 6584 KB Output is correct : V - N = 12
11 Correct 61 ms 7928 KB Output is correct : V - N = 12
12 Correct 357 ms 21084 KB Output is correct : V - N = 12
13 Correct 687 ms 32544 KB Output is correct : V - N = 12
14 Correct 770 ms 32912 KB Output is correct : V - N = 12
15 Correct 498 ms 27252 KB Output is correct : V - N = 12
16 Correct 103 ms 9072 KB Output is correct : V - N = 12
17 Correct 23 ms 5912 KB Output is correct : V - N = 12
18 Correct 310 ms 17336 KB Output is correct : V - N = 12
19 Correct 554 ms 31068 KB Output is correct : V - N = 12
20 Correct 645 ms 33776 KB Output is correct : V - N = 12
21 Correct 218 ms 13540 KB Output is correct : V - N = 12
22 Correct 134 ms 11456 KB Output is correct : V - N = 12
23 Correct 70 ms 8068 KB Output is correct : V - N = 12
24 Correct 6 ms 4976 KB Output is correct : V - N = 12
25 Correct 45 ms 6544 KB Output is correct : V - N = 12
26 Correct 113 ms 10952 KB Output is correct : V - N = 12
27 Correct 209 ms 12348 KB Output is correct : V - N = 12
28 Correct 155 ms 11920 KB Output is correct : V - N = 12
29 Correct 102 ms 8584 KB Output is correct : V - N = 12
30 Correct 11 ms 5420 KB Output is correct : V - N = 12
31 Correct 9 ms 5040 KB Output is correct : V - N = 12
32 Correct 10 ms 5032 KB Output is correct : V - N = 12
33 Correct 10 ms 5064 KB Output is correct : V - N = 12
34 Correct 9 ms 5328 KB Output is correct : V - N = 12
35 Correct 9 ms 5096 KB Output is correct : V - N = 12
36 Correct 686 ms 33452 KB Output is correct : V - N = 12
37 Correct 867 ms 33680 KB Output is correct : V - N = 12
38 Correct 696 ms 33440 KB Output is correct : V - N = 12
39 Correct 614 ms 33524 KB Output is correct : V - N = 12
40 Correct 851 ms 33384 KB Output is correct : V - N = 12
41 Correct 138 ms 11048 KB Output is correct : V - N = 12
42 Correct 126 ms 9600 KB Output is correct : V - N = 12
43 Correct 108 ms 10608 KB Output is correct : V - N = 12
44 Correct 11 ms 5136 KB Output is correct : V - N = 12
45 Correct 72 ms 8248 KB Output is correct : V - N = 12
46 Correct 214 ms 16712 KB Output is correct : V - N = 12
47 Correct 126 ms 10980 KB Output is correct : V - N = 12
48 Correct 389 ms 18528 KB Output is correct : V - N = 12
49 Correct 73 ms 7796 KB Output is correct : V - N = 12
50 Correct 24 ms 5972 KB Output is correct : V - N = 12
51 Correct 592 ms 30068 KB Output is correct : V - N = 12
52 Correct 13 ms 5360 KB Output is correct : V - N = 12
53 Correct 554 ms 28132 KB Output is correct : V - N = 12
54 Correct 680 ms 31488 KB Output is correct : V - N = 12
55 Correct 48 ms 6648 KB Output is correct : V - N = 12
56 Correct 407 ms 20340 KB Output is correct : V - N = 12
57 Correct 721 ms 32668 KB Output is correct : V - N = 12
58 Correct 121 ms 8916 KB Output is correct : V - N = 12
59 Correct 325 ms 17088 KB Output is correct : V - N = 12
60 Correct 801 ms 32868 KB Output is correct : V - N = 12
61 Correct 4 ms 4840 KB Output is correct : V - N = 12
62 Correct 4 ms 4824 KB Output is correct : V - N = 12
63 Correct 3 ms 4716 KB Output is correct : V - N = 12
64 Correct 3 ms 4640 KB Output is correct : V - N = 12
65 Correct 3 ms 4644 KB Output is correct : V - N = 12
66 Correct 4 ms 4848 KB Output is correct : V - N = 12
67 Correct 4 ms 4848 KB Output is correct : V - N = 12
68 Correct 4 ms 4844 KB Output is correct : V - N = 12
69 Correct 3 ms 4716 KB Output is correct : V - N = 12
70 Correct 3 ms 4808 KB Output is correct : V - N = 12
71 Correct 3 ms 4716 KB Output is correct : V - N = 12
72 Correct 3 ms 4628 KB Output is correct : V - N = 12
73 Correct 4 ms 4772 KB Output is correct : V - N = 12
74 Correct 4 ms 4796 KB Output is correct : V - N = 12
75 Correct 3 ms 4836 KB Output is correct : V - N = 12
76 Correct 3 ms 4708 KB Output is correct : V - N = 12
77 Correct 3 ms 4716 KB Output is correct : V - N = 12
78 Correct 3 ms 4652 KB Output is correct : V - N = 12
79 Correct 5 ms 4844 KB Output is correct : V - N = 12
80 Correct 4 ms 4848 KB Output is correct : V - N = 12
81 Correct 4 ms 4772 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 3 ms 4716 KB Output is correct : V - N = 12
85 Correct 3 ms 4656 KB Output is correct : V - N = 12
86 Correct 4 ms 4724 KB Output is correct : V - N = 12
87 Correct 3 ms 4768 KB Output is correct : V - N = 12
88 Correct 3 ms 4844 KB Output is correct : V - N = 12
89 Correct 4 ms 4644 KB Output is correct : V - N = 12
90 Correct 3 ms 4696 KB Output is correct : V - N = 12
91 Correct 3 ms 4712 KB Output is correct : V - N = 12
92 Correct 3 ms 4784 KB Output is correct : V - N = 12
93 Correct 4 ms 4712 KB Output is correct : V - N = 12
94 Correct 3 ms 4708 KB Output is correct : V - N = 12
95 Correct 3 ms 4712 KB Output is correct : V - N = 12
96 Correct 4 ms 4864 KB Output is correct : V - N = 12
97 Correct 4 ms 4852 KB Output is correct : V - N = 12
98 Correct 4 ms 4844 KB Output is correct : V - N = 12
99 Correct 4 ms 4828 KB Output is correct : V - N = 12
100 Correct 3 ms 4840 KB Output is correct : V - N = 12
101 Correct 3 ms 4644 KB Output is correct : V - N = 12
102 Correct 5 ms 4696 KB Output is correct : V - N = 12
103 Correct 3 ms 4720 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 4 ms 4708 KB Output is correct : V - N = 12
107 Correct 3 ms 4624 KB Output is correct : V - N = 12
108 Correct 3 ms 4624 KB Output is correct : V - N = 12
109 Correct 3 ms 4700 KB Output is correct : V - N = 12
110 Correct 3 ms 4644 KB Output is correct : V - N = 12
111 Correct 3 ms 4844 KB Output is correct : V - N = 12
112 Correct 3 ms 4712 KB Output is correct : V - N = 12
113 Correct 3 ms 4732 KB Output is correct : V - N = 12
114 Correct 3 ms 4716 KB Output is correct : V - N = 12
115 Correct 3 ms 4708 KB Output is correct : V - N = 12
116 Correct 3 ms 4664 KB Output is correct : V - N = 12
117 Correct 4 ms 4780 KB Output is correct : V - N = 12
118 Correct 3 ms 4716 KB Output is correct : V - N = 12
119 Correct 3 ms 4724 KB Output is correct : V - N = 12
120 Correct 4 ms 4636 KB Output is correct : V - N = 12
121 Correct 3 ms 4640 KB Output is correct : V - N = 12
122 Correct 3 ms 4716 KB Output is correct : V - N = 12
123 Correct 3 ms 4716 KB Output is correct : V - N = 12
124 Correct 3 ms 4748 KB Output is correct : V - N = 12
125 Correct 4 ms 4696 KB Output is correct : V - N = 12
126 Correct 4 ms 4700 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 3 ms 4624 KB Output is correct : V - N = 12
130 Correct 4 ms 4584 KB Output is correct : V - N = 12
131 Correct 3 ms 4644 KB Output is correct : V - N = 12
132 Correct 4 ms 4624 KB Output is correct : V - N = 12
133 Correct 3 ms 4696 KB Output is correct : V - N = 12
134 Correct 5 ms 4636 KB Output is correct : V - N = 12
135 Correct 4 ms 4696 KB Output is correct : V - N = 12
136 Correct 4 ms 4644 KB Output is correct : V - N = 12
137 Correct 3 ms 4640 KB Output is correct : V - N = 12
138 Correct 3 ms 4716 KB Output is correct : V - N = 12
139 Correct 3 ms 4712 KB Output is correct : V - N = 12
140 Correct 3 ms 4716 KB Output is correct : V - N = 12
141 Correct 3 ms 4712 KB Output is correct : V - N = 12
142 Correct 4 ms 4656 KB Output is correct : V - N = 12
143 Correct 3 ms 4596 KB Output is correct : V - N = 12
144 Correct 4 ms 4692 KB Output is correct : V - N = 12
145 Correct 3 ms 4720 KB Output is correct : V - N = 12
146 Correct 3 ms 4676 KB Output is correct : V - N = 12
147 Correct 4 ms 4624 KB Output is correct : V - N = 12
148 Correct 3 ms 4696 KB Output is correct : V - N = 12
149 Correct 4 ms 4560 KB Output is correct : V - N = 12
150 Correct 4 ms 4592 KB Output is correct : V - N = 12
151 Correct 3 ms 4712 KB Output is correct : V - N = 12
152 Correct 3 ms 4624 KB Output is correct : V - N = 12
153 Correct 3 ms 4724 KB Output is correct : V - N = 12
154 Correct 3 ms 4592 KB Output is correct : V - N = 12
155 Correct 3 ms 4624 KB Output is correct : V - N = 12
156 Correct 4 ms 4708 KB Output is correct : V - N = 12
157 Correct 5 ms 4624 KB Output is correct : V - N = 12
158 Correct 3 ms 4644 KB Output is correct : V - N = 12
159 Correct 3 ms 4716 KB Output is correct : V - N = 12
160 Correct 3 ms 4624 KB Output is correct : V - N = 12
161 Correct 3 ms 4624 KB Output is correct : V - N = 12
162 Correct 3 ms 4724 KB Output is correct : V - N = 12
163 Correct 4 ms 4716 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 4716 KB Output is correct : V - N = 12
167 Correct 4 ms 4632 KB Output is correct : V - N = 12
168 Correct 4 ms 4716 KB Output is correct : V - N = 12
169 Correct 4 ms 4712 KB Output is correct : V - N = 12
170 Correct 4 ms 4624 KB Output is correct : V - N = 12
171 Incorrect 3 ms 4624 KB Wrong Answer [11]
172 Halted 0 ms 0 KB -