oj.uz

Submission #260410

# Submission time Handle Problem Language Result Execution time Memory
260410 2020-08-10T08:32:51 Z 반딧불(#5056) Airline Route Map (JOI18_airline) C++14
0 / 100
 955 ms 39376 KB 
#include <bits/stdc++.h>
#include "Alicelib.h"

using namespace std;

typedef long long ll;

namespace AA{
    vector<int> link[1020];
    vector<pair<int, int> > edge;
    int cnt = 1;
}
using namespace AA;

void Alice(int N, int M, int A[], int B[]){
    for(int i=0; i<M; i++){ /// original graph
        link[A[i]].push_back(B[i]);
        link[B[i]].push_back(A[i]);
    }
    for(int i=0; i<N+10; i++){ /// vertex X
        link[N+11].push_back(i);
        link[i].push_back(N+11);
    }
    for(int d=0; d<10; d++){ /// vertex d0, d1, ..., d9
        for(int i=0; i<N; i++){
            if(i & (1<<d)) link[i].push_back(N+d), link[N+d].push_back(i);
        }
    }

    for(int i=0; i<10; i++){
        link[N+i].push_back(N+10);
        link[N+10].push_back(N+i);
    }

    for(int i=0; i<9; i++){
        link[N+i].push_back(N+i+1);
        link[N+i+1].push_back(N+i);
    }

    for(int i=0; i<N+12; i++){
        for(auto &j: link[i]){
            if(i < j) edge.push_back(make_pair(i, j));
        }
    }

    InitG(N+12, (int)edge.size());
    int cnt = 0;
    for(auto &x: edge){
        MakeG(cnt++, x.first, x.second);
    }
}

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

using namespace std;

typedef long long ll;

namespace BB{
    int n, m;
    int idx[1020];
    vector<int> glink[1020];
    vector<int> link[1002];

    int vertexX = -1, vertexY = -1;
    int vertexD[10];
    vector<int> specialVertices;
    bool isSpecial[1020];
    int specialDegree[1020];

    vector<int> specialLink[1020];

    vector<pair<int, int> > edge;
}
using namespace BB;

void Bob(int V, int U, int C[], int D[]){
    n = V-12;
    if(n==1){
        InitMap(1, 0);
        return;
    }

    for(int i=0; i<U; i++){
        glink[C[i]].push_back(D[i]);
        glink[D[i]].push_back(C[i]);
    }

    for(int i=0; i<V; i++){
        if((int)glink[i].size() == n+10){
            vertexX = i;

            for(int j=0; j<V; j++) isSpecial[j] = 1;
            isSpecial[i] = 0;
            for(auto &x: glink[i]) isSpecial[x] = 0;

            for(int j=0; j<V; j++){
                if(isSpecial[j]) specialVertices.push_back(j);
            }
            vertexY = specialVertices[0];
            isSpecial[vertexY] = 0;

            if(specialVertices.size() != 1){
                InitMap(0, 0);
                InitMap(0, 0);
                exit(0);
            }

            specialVertices.clear();
            for(auto &x: glink[vertexY]){
                specialVertices.push_back(x);
                isSpecial[x] = 1;
            }
            assert(specialVertices.size() == 10);
            break;
        }
    }

    int onedeg = 0;
    for(auto &x: specialVertices){
        for(auto &y: glink[x]){
            if(isSpecial[y]){
                specialDegree[x]++;
                specialLink[x].push_back(y);
                specialLink[y].push_back(x);
            }
        }
        if(specialDegree[x] == 1) onedeg = max(onedeg, (int)glink[x].size());
    }
    for(auto &x: specialVertices){
        if(specialDegree[x] == 1 && onedeg == (int)glink[x].size()){
            vertexD[0] = x;
            specialDegree[x] = 0;

            int tmp = x, prv = 0;
            for(int i=1; i<10; i++){
                vertexD[i] = -1;
                for(auto &y: specialLink[tmp]){
                    if(prv == y) continue;
                    prv = tmp;
                    vertexD[i] = tmp = y;
                    specialDegree[y] = i;
                    break;
                }
            }
            break;
        }
    }

    for(int i=0; i<V; i++){
        if(isSpecial[i] || i == vertexX || i == vertexY) continue;

        for(auto &x: glink[i]){
            if(isSpecial[x]) idx[i] += 1 << specialDegree[x];
        }
    }

    for(int i=0; i<V; i++){
        if(isSpecial[i] || i == vertexX || i == vertexY) continue;

        for(auto &x: glink[i]){
            if(!isSpecial[x] && x != vertexX && x != vertexY){
                link[idx[i]].push_back(idx[x]);
            }
        }
    }

    for(int i=0; i<n; i++){
        for(auto &x: link[i]){
            if(i < x){
                edge.push_back(make_pair(i, x));
            }
        }
    }

    InitMap(n, (int)edge.size());
    for(auto &x: edge){
        MakeMap(x.first, x.second);
    }
}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 39376 KB Output is correct : V - N = 12
2 Correct 605 ms 34488 KB Output is correct : V - N = 12
3 Correct 212 ms 18984 KB Output is correct : V - N = 12
4 Correct 15 ms 7680 KB Output is correct : V - N = 12
5 Correct 189 ms 14000 KB Output is correct : V - N = 12
6 Correct 462 ms 32472 KB Output is correct : V - N = 12
7 Correct 686 ms 39096 KB Output is correct : V - N = 12
8 Correct 602 ms 36944 KB Output is correct : V - N = 12
9 Correct 312 ms 22168 KB Output is correct : V - N = 12
10 Correct 47 ms 9200 KB Output is correct : V - N = 12
11 Correct 75 ms 10672 KB Output is correct : V - N = 12
12 Correct 368 ms 25856 KB Output is correct : V - N = 12
13 Correct 663 ms 37912 KB Output is correct : V - N = 12
14 Correct 673 ms 38688 KB Output is correct : V - N = 12
15 Correct 418 ms 31612 KB Output is correct : V - N = 12
16 Correct 89 ms 12096 KB Output is correct : V - N = 12
17 Correct 20 ms 8440 KB Output is correct : V - N = 12
18 Correct 299 ms 20600 KB Output is correct : V - N = 12
19 Correct 611 ms 35976 KB Output is correct : V - N = 12
20 Correct 727 ms 39368 KB Output is correct : V - N = 12
21 Correct 191 ms 17896 KB Output is correct : V - N = 12
22 Correct 147 ms 14432 KB Output is correct : V - N = 12
23 Correct 68 ms 10456 KB Output is correct : V - N = 12
24 Correct 9 ms 7168 KB Output is correct : V - N = 12
25 Correct 40 ms 9160 KB Output is correct : V - N = 12
26 Correct 134 ms 13704 KB Output is correct : V - N = 12
27 Correct 188 ms 16016 KB Output is correct : V - N = 12
28 Correct 168 ms 15128 KB Output is correct : V - N = 12
29 Correct 89 ms 11576 KB Output is correct : V - N = 12
30 Correct 13 ms 7928 KB Output is correct : V - N = 12
31 Correct 12 ms 7424 KB Output is correct : V - N = 12
32 Correct 12 ms 7424 KB Output is correct : V - N = 12
33 Correct 13 ms 7424 KB Output is correct : V - N = 12
34 Correct 15 ms 7424 KB Output is correct : V - N = 12
35 Correct 12 ms 7424 KB Output is correct : V - N = 12
36 Correct 803 ms 39256 KB Output is correct : V - N = 12
37 Correct 704 ms 39168 KB Output is correct : V - N = 12
38 Correct 955 ms 39240 KB Output is correct : V - N = 12
39 Correct 701 ms 39240 KB Output is correct : V - N = 12
40 Correct 856 ms 39168 KB Output is correct : V - N = 12
41 Correct 123 ms 13600 KB Output is correct : V - N = 12
42 Correct 107 ms 12552 KB Output is correct : V - N = 12
43 Correct 192 ms 13336 KB Output is correct : V - N = 12
44 Correct 15 ms 7424 KB Output is correct : V - N = 12
45 Correct 69 ms 10792 KB Output is correct : V - N = 12
46 Correct 239 ms 19864 KB Output is correct : V - N = 12
47 Correct 120 ms 13600 KB Output is correct : V - N = 12
48 Correct 494 ms 22408 KB Output is correct : V - N = 12
49 Correct 66 ms 10424 KB Output is correct : V - N = 12
50 Correct 32 ms 8496 KB Output is correct : V - N = 12
51 Correct 857 ms 34496 KB Output is correct : V - N = 12
52 Correct 14 ms 7680 KB Output is correct : V - N = 12
53 Correct 472 ms 32184 KB Output is correct : V - N = 12
54 Correct 619 ms 36616 KB Output is correct : V - N = 12
55 Correct 47 ms 9208 KB Output is correct : V - N = 12
56 Correct 355 ms 24888 KB Output is correct : V - N = 12
57 Correct 662 ms 37856 KB Output is correct : V - N = 12
58 Correct 96 ms 11984 KB Output is correct : V - N = 12
59 Correct 269 ms 20392 KB Output is correct : V - N = 12
60 Correct 654 ms 38520 KB Output is correct : V - N = 12
61 Correct 6 ms 6912 KB Output is correct : V - N = 12
62 Correct 6 ms 6912 KB Output is correct : V - N = 12
63 Correct 5 ms 6912 KB Output is correct : V - N = 12
64 Correct 5 ms 6912 KB Output is correct : V - N = 12
65 Correct 5 ms 6912 KB Output is correct : V - N = 12
66 Correct 7 ms 6912 KB Output is correct : V - N = 12
67 Correct 6 ms 6912 KB Output is correct : V - N = 12
68 Correct 5 ms 6912 KB Output is correct : V - N = 12
69 Correct 5 ms 6912 KB Output is correct : V - N = 12
70 Correct 7 ms 6912 KB Output is correct : V - N = 12
71 Correct 5 ms 6912 KB Output is correct : V - N = 12
72 Correct 6 ms 6912 KB Output is correct : V - N = 12
73 Correct 6 ms 6912 KB Output is correct : V - N = 12
74 Correct 6 ms 6912 KB Output is correct : V - N = 12
75 Correct 6 ms 6912 KB Output is correct : V - N = 12
76 Correct 6 ms 6912 KB Output is correct : V - N = 12
77 Correct 6 ms 6912 KB Output is correct : V - N = 12
78 Correct 6 ms 6912 KB Output is correct : V - N = 12
79 Correct 6 ms 6912 KB Output is correct : V - N = 12
80 Correct 6 ms 6912 KB Output is correct : V - N = 12
81 Correct 6 ms 6912 KB Output is correct : V - N = 12
82 Correct 6 ms 6976 KB Output is correct : V - N = 12
83 Correct 7 ms 6912 KB Output is correct : V - N = 12
84 Correct 5 ms 7168 KB Output is correct : V - N = 12
85 Correct 5 ms 6912 KB Output is correct : V - N = 12
86 Correct 6 ms 6912 KB Output is correct : V - N = 12
87 Correct 7 ms 6912 KB Output is correct : V - N = 12
88 Correct 7 ms 6912 KB Output is correct : V - N = 12
89 Correct 6 ms 6912 KB Output is correct : V - N = 12
90 Correct 6 ms 6912 KB Output is correct : V - N = 12
91 Correct 6 ms 6912 KB Output is correct : V - N = 12
92 Correct 5 ms 6912 KB Output is correct : V - N = 12
93 Correct 5 ms 6912 KB Output is correct : V - N = 12
94 Correct 5 ms 6912 KB Output is correct : V - N = 12
95 Correct 5 ms 6912 KB Output is correct : V - N = 12
96 Correct 7 ms 6912 KB Output is correct : V - N = 12
97 Correct 6 ms 7168 KB Output is correct : V - N = 12
98 Correct 7 ms 6912 KB Output is correct : V - N = 12
99 Correct 7 ms 6912 KB Output is correct : V - N = 12
100 Correct 7 ms 7168 KB Output is correct : V - N = 12
101 Correct 6 ms 6912 KB Output is correct : V - N = 12
102 Correct 6 ms 6912 KB Output is correct : V - N = 12
103 Correct 6 ms 6912 KB Output is correct : V - N = 12
104 Correct 5 ms 7168 KB Output is correct : V - N = 12
105 Correct 5 ms 6912 KB Output is correct : V - N = 12
106 Correct 5 ms 6912 KB Output is correct : V - N = 12
107 Correct 6 ms 6912 KB Output is correct : V - N = 12
108 Correct 5 ms 6912 KB Output is correct : V - N = 12
109 Correct 5 ms 6912 KB Output is correct : V - N = 12
110 Incorrect 5 ms 6912 KB Wrong Answer [11]
111 Halted 0 ms 0 KB -