oj.uz

Submission #320182

# Submission time Handle Problem Language Result Execution time Memory
320182 2020-11-07T21:26:59 Z thecodingwizard Airline Route Map (JOI18_airline) C++11
0 / 100
 1121 ms 27132 KB 
#include <bits/stdc++.h>
using namespace std;
#include "Alicelib.h"

void Alice( int N, int M, int A[], int B[] ){
    vector<int> adj[N+12];
    for (int i = 0; i < 9; i++) {
        adj[i].push_back(i+1);
    }
    for (int i = 12; i < N+12; i++) {
        adj[11].push_back(i);
        for (int j = 0; j < 10; j++) {
            if ((i-11) & (1 << j)) {
                adj[i].push_back(j);
            }
        }
    }
    for (int i = 0; i < M; i++) {
        adj[A[i]+12].push_back(B[i]+12);
    }
    adj[10].push_back(11); // special identifying node

    int edgeCt = 0;
    for (int i = 0; i < N+12; i++) edgeCt += adj[i].size();
    InitG(N+12, edgeCt);
    int ctr = 0;
    for (int i = 0; i < N+12; i++) {
        for (int j : adj[i]) {
            MakeG(ctr++, i, j);
        }
    }
}


#include <bits/stdc++.h>
using namespace std;
#include "Boblib.h"

void Bob( int V, int U, int C[], int D[] ){
    vector<int> adj[V];
    for (int i = 0; i < U; i++) {
        adj[C[i]].push_back(D[i]);
        adj[D[i]].push_back(C[i]);
    }
    map<int, int> realID;
    int excludeBits = -1;
    for (int i = 0; i < V; i++) {
        if (adj[i].size() == 1) {
            if ((int)adj[adj[i][0]].size() == V-11) {
                assert(excludeBits == -1);
                excludeBits = adj[i][0];
                realID[i] = -1;
            }
        }
    }
    assert(excludeBits != -1);
    set<int> bitNodesSet;
    for (int i = 0; i < V; i++) {
        bitNodesSet.insert(i);
    }
    for (int j : adj[excludeBits]) bitNodesSet.erase(j);
    bitNodesSet.erase(excludeBits);
    assert(bitNodesSet.size() == 10);
    int largestBit = *bitNodesSet.begin();
    for (int x : bitNodesSet) {
        if (adj[largestBit].size() > adj[x].size()) largestBit = x;
    }
    vector<int> bitNodes;
    int cur = largestBit;
    while (cur != -1) {
        bitNodes.push_back(cur);
        int nxt = -1;
        for (int v : adj[cur]) {
            if (bitNodesSet.count(v) && find(bitNodes.begin(), bitNodes.end(), v) == bitNodes.end()) {
                assert(nxt == -1);
                nxt = v;
            }
        }
        cur = nxt;
    }
    assert(bitNodes.size() == 10);
    reverse(bitNodes.begin(), bitNodes.end());
    realID[excludeBits] = -1;
    for (int x : bitNodes) realID[x] = -1;
    for (int i = 0; i < V; i++) {
        if (realID[i] != -1) {
            int v = 0;
            for (int j : adj[i]) {
                auto it = find(bitNodes.begin(), bitNodes.end(), j);
                if (it == bitNodes.end()) continue;
                int val = it - bitNodes.begin();
                v |= (1 << val);
            }
            realID[i] = v-1;
            assert(0 <= v-1 && v-1 < V-12);
        }
    }
    vector<int> realAdj[V-12];
    for (int i = 0; i < V; i++) {
        if (realID[i] != -1) {
            for (int j : adj[i]) {
                if (realID[j] == -1) continue;
                int a = realID[i], b = realID[j];
                if (a < b) {
                    realAdj[a].push_back(b);
                }
            }
        }
    }
    int edgeCt = 0;
    for (int i = 0; i < V-12; i++) edgeCt += realAdj[i].size();
	InitMap( V-12, edgeCt );
    for (int i = 0; i < V-12; i++) {
        for (int j : realAdj[i]) {
            MakeMap(i, j);
        }
    }
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4928 KB Output is correct
2 Correct 5 ms 4960 KB Output is correct
3 Correct 5 ms 4832 KB Output is correct
4 Correct 5 ms 4992 KB Output is correct
5 Correct 5 ms 4920 KB Output is correct
6 Correct 5 ms 4932 KB Output is correct
7 Correct 5 ms 4832 KB Output is correct
8 Correct 7 ms 4832 KB Output is correct
9 Correct 5 ms 4832 KB Output is correct
10 Correct 5 ms 5088 KB Output is correct
11 Correct 7 ms 4992 KB Output is correct
12 Correct 5 ms 4896 KB Output is correct
13 Correct 5 ms 4832 KB Output is correct
14 Correct 5 ms 4864 KB Output is correct
15 Correct 6 ms 4980 KB Output is correct
16 Correct 5 ms 4928 KB Output is correct
17 Correct 5 ms 4936 KB Output is correct
18 Correct 6 ms 5076 KB Output is correct
19 Correct 5 ms 4832 KB Output is correct
20 Correct 7 ms 4832 KB Output is correct
21 Correct 5 ms 4928 KB Output is correct
22 Correct 5 ms 4992 KB Output is correct
23 Correct 6 ms 4832 KB Output is correct
24 Correct 5 ms 4940 KB Output is correct
25 Correct 5 ms 4920 KB Output is correct
26 Correct 6 ms 5128 KB Output is correct
27 Correct 5 ms 4928 KB Output is correct
28 Correct 6 ms 4832 KB Output is correct
29 Correct 5 ms 4832 KB Output is correct
30 Correct 6 ms 4832 KB Output is correct
31 Correct 6 ms 4932 KB Output is correct
32 Correct 6 ms 4952 KB Output is correct
33 Correct 7 ms 4864 KB Output is correct
34 Correct 5 ms 4832 KB Output is correct
35 Correct 5 ms 4932 KB Output is correct
36 Correct 6 ms 4832 KB Output is correct
37 Correct 5 ms 4920 KB Output is correct
38 Correct 6 ms 4928 KB Output is correct
39 Correct 5 ms 4832 KB Output is correct
40 Correct 5 ms 4928 KB Output is correct
41 Correct 5 ms 4924 KB Output is correct
42 Correct 6 ms 4832 KB Output is correct
43 Correct 5 ms 4832 KB Output is correct
44 Correct 5 ms 4948 KB Output is correct
45 Correct 5 ms 4928 KB Output is correct
46 Correct 5 ms 4924 KB Output is correct
47 Correct 5 ms 4832 KB Output is correct
48 Correct 5 ms 4832 KB Output is correct
49 Correct 6 ms 4832 KB Output is correct
50 Correct 5 ms 4936 KB Output is correct
51 Runtime error 10 ms 6368 KB Execution killed with signal 6 (could be triggered by violating memory limits)
52 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4928 KB Output is correct
2 Correct 5 ms 4960 KB Output is correct
3 Correct 5 ms 4832 KB Output is correct
4 Correct 5 ms 4992 KB Output is correct
5 Correct 5 ms 4920 KB Output is correct
6 Correct 5 ms 4932 KB Output is correct
7 Correct 5 ms 4832 KB Output is correct
8 Correct 7 ms 4832 KB Output is correct
9 Correct 5 ms 4832 KB Output is correct
10 Correct 5 ms 5088 KB Output is correct
11 Correct 7 ms 4992 KB Output is correct
12 Correct 5 ms 4896 KB Output is correct
13 Correct 5 ms 4832 KB Output is correct
14 Correct 5 ms 4864 KB Output is correct
15 Correct 6 ms 4980 KB Output is correct
16 Correct 5 ms 4928 KB Output is correct
17 Correct 5 ms 4936 KB Output is correct
18 Correct 6 ms 5076 KB Output is correct
19 Correct 5 ms 4832 KB Output is correct
20 Correct 7 ms 4832 KB Output is correct
21 Correct 5 ms 4928 KB Output is correct
22 Correct 5 ms 4992 KB Output is correct
23 Correct 6 ms 4832 KB Output is correct
24 Correct 5 ms 4940 KB Output is correct
25 Correct 5 ms 4920 KB Output is correct
26 Correct 6 ms 5128 KB Output is correct
27 Correct 5 ms 4928 KB Output is correct
28 Correct 6 ms 4832 KB Output is correct
29 Correct 5 ms 4832 KB Output is correct
30 Correct 6 ms 4832 KB Output is correct
31 Correct 6 ms 4932 KB Output is correct
32 Correct 6 ms 4952 KB Output is correct
33 Correct 7 ms 4864 KB Output is correct
34 Correct 5 ms 4832 KB Output is correct
35 Correct 5 ms 4932 KB Output is correct
36 Correct 6 ms 4832 KB Output is correct
37 Correct 5 ms 4920 KB Output is correct
38 Correct 6 ms 4928 KB Output is correct
39 Correct 5 ms 4832 KB Output is correct
40 Correct 5 ms 4928 KB Output is correct
41 Correct 5 ms 4924 KB Output is correct
42 Correct 6 ms 4832 KB Output is correct
43 Correct 5 ms 4832 KB Output is correct
44 Correct 5 ms 4948 KB Output is correct
45 Correct 5 ms 4928 KB Output is correct
46 Correct 5 ms 4924 KB Output is correct
47 Correct 5 ms 4832 KB Output is correct
48 Correct 5 ms 4832 KB Output is correct
49 Correct 6 ms 4832 KB Output is correct
50 Correct 5 ms 4936 KB Output is correct
51 Runtime error 10 ms 6368 KB Execution killed with signal 6 (could be triggered by violating memory limits)
52 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 27132 KB Output is correct : V - N = 12
2 Correct 677 ms 22980 KB Output is correct : V - N = 12
3 Correct 288 ms 12656 KB Output is correct : V - N = 12
4 Correct 17 ms 5584 KB Output is correct : V - N = 12
5 Correct 209 ms 9568 KB Output is correct : V - N = 12
6 Correct 600 ms 20776 KB Output is correct : V - N = 12
7 Correct 859 ms 26260 KB Output is correct : V - N = 12
8 Correct 916 ms 24648 KB Output is correct : V - N = 12
9 Correct 421 ms 14788 KB Output is correct : V - N = 12
10 Correct 42 ms 6392 KB Output is correct : V - N = 12
11 Correct 72 ms 7180 KB Output is correct : V - N = 12
12 Correct 485 ms 16860 KB Output is correct : V - N = 12
13 Correct 959 ms 25408 KB Output is correct : V - N = 12
14 Correct 804 ms 25728 KB Output is correct : V - N = 12
15 Correct 556 ms 19328 KB Output is correct : V - N = 12
16 Correct 138 ms 8088 KB Output is correct : V - N = 12
17 Correct 28 ms 5756 KB Output is correct : V - N = 12
18 Correct 331 ms 13756 KB Output is correct : V - N = 12
19 Correct 763 ms 23916 KB Output is correct : V - N = 12
20 Correct 821 ms 26404 KB Output is correct : V - N = 12
21 Correct 222 ms 11668 KB Output is correct : V - N = 12
22 Correct 170 ms 9776 KB Output is correct : V - N = 12
23 Correct 65 ms 7400 KB Output is correct : V - N = 12
24 Correct 9 ms 4964 KB Output is correct : V - N = 12
25 Correct 49 ms 6208 KB Output is correct : V - N = 12
26 Correct 195 ms 9212 KB Output is correct : V - N = 12
27 Correct 260 ms 10636 KB Output is correct : V - N = 12
28 Correct 253 ms 10296 KB Output is correct : V - N = 12
29 Correct 104 ms 7668 KB Output is correct : V - N = 12
30 Correct 15 ms 5336 KB Output is correct : V - N = 12
31 Correct 12 ms 5320 KB Output is correct : V - N = 12
32 Correct 12 ms 5308 KB Output is correct : V - N = 12
33 Correct 12 ms 5220 KB Output is correct : V - N = 12
34 Correct 12 ms 5216 KB Output is correct : V - N = 12
35 Correct 13 ms 5308 KB Output is correct : V - N = 12
36 Correct 1090 ms 26584 KB Output is correct : V - N = 12
37 Correct 915 ms 26672 KB Output is correct : V - N = 12
38 Correct 879 ms 26644 KB Output is correct : V - N = 12
39 Correct 1121 ms 26308 KB Output is correct : V - N = 12
40 Correct 927 ms 26652 KB Output is correct : V - N = 12
41 Correct 160 ms 9384 KB Output is correct : V - N = 12
42 Correct 156 ms 8476 KB Output is correct : V - N = 12
43 Correct 141 ms 8760 KB Output is correct : V - N = 12
44 Correct 13 ms 5248 KB Output is correct : V - N = 12
45 Correct 108 ms 7392 KB Output is correct : V - N = 12
46 Correct 306 ms 13008 KB Output is correct : V - N = 12
47 Correct 143 ms 9224 KB Output is correct : V - N = 12
48 Correct 431 ms 15224 KB Output is correct : V - N = 12
49 Correct 78 ms 6968 KB Output is correct : V - N = 12
50 Correct 25 ms 5748 KB Output is correct : V - N = 12
51 Correct 714 ms 22868 KB Output is correct : V - N = 12
52 Correct 15 ms 5592 KB Output is correct : V - N = 12
53 Correct 540 ms 20676 KB Output is correct : V - N = 12
54 Correct 951 ms 24368 KB Output is correct : V - N = 12
55 Correct 57 ms 6352 KB Output is correct : V - N = 12
56 Correct 471 ms 16260 KB Output is correct : V - N = 12
57 Correct 779 ms 25504 KB Output is correct : V - N = 12
58 Correct 129 ms 8056 KB Output is correct : V - N = 12
59 Correct 339 ms 13548 KB Output is correct : V - N = 12
60 Correct 859 ms 25908 KB Output is correct : V - N = 12
61 Correct 7 ms 4832 KB Output is correct : V - N = 12
62 Correct 7 ms 4852 KB Output is correct : V - N = 12
63 Correct 6 ms 4920 KB Output is correct : V - N = 12
64 Correct 5 ms 4932 KB Output is correct : V - N = 12
65 Correct 5 ms 4832 KB Output is correct : V - N = 12
66 Correct 6 ms 4916 KB Output is correct : V - N = 12
67 Correct 7 ms 4896 KB Output is correct : V - N = 12
68 Correct 7 ms 4864 KB Output is correct : V - N = 12
69 Correct 6 ms 4912 KB Output is correct : V - N = 12
70 Correct 7 ms 4832 KB Output is correct : V - N = 12
71 Correct 6 ms 4832 KB Output is correct : V - N = 12
72 Correct 5 ms 4960 KB Output is correct : V - N = 12
73 Correct 7 ms 4832 KB Output is correct : V - N = 12
74 Correct 8 ms 4832 KB Output is correct : V - N = 12
75 Correct 6 ms 4832 KB Output is correct : V - N = 12
76 Correct 5 ms 4916 KB Output is correct : V - N = 12
77 Correct 5 ms 4832 KB Output is correct : V - N = 12
78 Correct 6 ms 4916 KB Output is correct : V - N = 12
79 Correct 7 ms 4832 KB Output is correct : V - N = 12
80 Correct 7 ms 4832 KB Output is correct : V - N = 12
81 Correct 7 ms 4832 KB Output is correct : V - N = 12
82 Correct 6 ms 4904 KB Output is correct : V - N = 12
83 Correct 7 ms 4832 KB Output is correct : V - N = 12
84 Correct 6 ms 4832 KB Output is correct : V - N = 12
85 Correct 6 ms 4852 KB Output is correct : V - N = 12
86 Correct 7 ms 4752 KB Output is correct : V - N = 12
87 Correct 6 ms 4832 KB Output is correct : V - N = 12
88 Correct 6 ms 4832 KB Output is correct : V - N = 12
89 Correct 7 ms 4920 KB Output is correct : V - N = 12
90 Correct 5 ms 4836 KB Output is correct : V - N = 12
91 Correct 6 ms 4832 KB Output is correct : V - N = 12
92 Correct 6 ms 4832 KB Output is correct : V - N = 12
93 Correct 5 ms 4944 KB Output is correct : V - N = 12
94 Correct 5 ms 4832 KB Output is correct : V - N = 12
95 Correct 5 ms 4940 KB Output is correct : V - N = 12
96 Correct 7 ms 4964 KB Output is correct : V - N = 12
97 Correct 6 ms 4876 KB Output is correct : V - N = 12
98 Correct 6 ms 4904 KB Output is correct : V - N = 12
99 Correct 6 ms 4912 KB Output is correct : V - N = 12
100 Correct 7 ms 4832 KB Output is correct : V - N = 12
101 Correct 6 ms 4832 KB Output is correct : V - N = 12
102 Correct 5 ms 4908 KB Output is correct : V - N = 12
103 Correct 5 ms 4920 KB Output is correct : V - N = 12
104 Correct 5 ms 4832 KB Output is correct : V - N = 12
105 Correct 5 ms 4992 KB Output is correct : V - N = 12
106 Correct 6 ms 4832 KB Output is correct : V - N = 12
107 Correct 6 ms 4924 KB Output is correct : V - N = 12
108 Correct 6 ms 4920 KB Output is correct : V - N = 12
109 Correct 5 ms 4988 KB Output is correct : V - N = 12
110 Correct 6 ms 4920 KB Output is correct : V - N = 12
111 Correct 6 ms 4832 KB Output is correct : V - N = 12
112 Correct 6 ms 5004 KB Output is correct : V - N = 12
113 Correct 6 ms 4832 KB Output is correct : V - N = 12
114 Correct 5 ms 4832 KB Output is correct : V - N = 12
115 Correct 5 ms 4920 KB Output is correct : V - N = 12
116 Correct 5 ms 4916 KB Output is correct : V - N = 12
117 Correct 6 ms 4844 KB Output is correct : V - N = 12
118 Correct 5 ms 4844 KB Output is correct : V - N = 12
119 Correct 5 ms 4920 KB Output is correct : V - N = 12
120 Correct 6 ms 4844 KB Output is correct : V - N = 12
121 Correct 5 ms 4844 KB Output is correct : V - N = 12
122 Correct 5 ms 4836 KB Output is correct : V - N = 12
123 Correct 5 ms 4924 KB Output is correct : V - N = 12
124 Correct 5 ms 4832 KB Output is correct : V - N = 12
125 Correct 5 ms 4832 KB Output is correct : V - N = 12
126 Correct 5 ms 4920 KB Output is correct : V - N = 12
127 Correct 6 ms 4832 KB Output is correct : V - N = 12
128 Correct 5 ms 4832 KB Output is correct : V - N = 12
129 Correct 5 ms 4832 KB Output is correct : V - N = 12
130 Correct 6 ms 4832 KB Output is correct : V - N = 12
131 Correct 5 ms 4920 KB Output is correct : V - N = 12
132 Correct 5 ms 4928 KB Output is correct : V - N = 12
133 Correct 6 ms 4932 KB Output is correct : V - N = 12
134 Correct 5 ms 4992 KB Output is correct : V - N = 12
135 Correct 5 ms 4832 KB Output is correct : V - N = 12
136 Correct 5 ms 4876 KB Output is correct : V - N = 12
137 Correct 6 ms 4832 KB Output is correct : V - N = 12
138 Correct 5 ms 4832 KB Output is correct : V - N = 12
139 Correct 5 ms 4920 KB Output is correct : V - N = 12
140 Correct 5 ms 4832 KB Output is correct : V - N = 12
141 Correct 5 ms 4924 KB Output is correct : V - N = 12
142 Correct 5 ms 4928 KB Output is correct : V - N = 12
143 Correct 5 ms 4876 KB Output is correct : V - N = 12
144 Correct 5 ms 4892 KB Output is correct : V - N = 12
145 Correct 5 ms 4932 KB Output is correct : V - N = 12
146 Correct 5 ms 4836 KB Output is correct : V - N = 12
147 Correct 5 ms 4988 KB Output is correct : V - N = 12
148 Correct 5 ms 4932 KB Output is correct : V - N = 12
149 Correct 5 ms 4832 KB Output is correct : V - N = 12
150 Correct 5 ms 4832 KB Output is correct : V - N = 12
151 Correct 5 ms 4832 KB Output is correct : V - N = 12
152 Correct 6 ms 4876 KB Output is correct : V - N = 12
153 Correct 5 ms 4836 KB Output is correct : V - N = 12
154 Correct 6 ms 4932 KB Output is correct : V - N = 12
155 Correct 5 ms 4832 KB Output is correct : V - N = 12
156 Correct 5 ms 4932 KB Output is correct : V - N = 12
157 Correct 5 ms 4832 KB Output is correct : V - N = 12
158 Correct 5 ms 4832 KB Output is correct : V - N = 12
159 Correct 5 ms 4960 KB Output is correct : V - N = 12
160 Correct 5 ms 4832 KB Output is correct : V - N = 12
161 Correct 5 ms 4832 KB Output is correct : V - N = 12
162 Correct 5 ms 4832 KB Output is correct : V - N = 12
163 Correct 5 ms 4924 KB Output is correct : V - N = 12
164 Correct 5 ms 4832 KB Output is correct : V - N = 12
165 Correct 5 ms 4832 KB Output is correct : V - N = 12
166 Correct 6 ms 4836 KB Output is correct : V - N = 12
167 Correct 5 ms 4960 KB Output is correct : V - N = 12
168 Correct 5 ms 4832 KB Output is correct : V - N = 12
169 Correct 6 ms 4832 KB Output is correct : V - N = 12
170 Correct 5 ms 4832 KB Output is correct : V - N = 12
171 Runtime error 7 ms 6220 KB Execution killed with signal 6 (could be triggered by violating memory limits)
172 Halted 0 ms 0 KB -