답안 #260410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260410	2020-08-10T08:32:51 Z	반딧불(#5056)	항공 노선도 (JOI18_airline)	C++14	0 / 100	955 ms	39376 KB

Alice

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

Bob

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-