Submission #1071442

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1071442	2024-08-23T07:26:49 Z	abczz	Airline Route Map (JOI18_airline)	C++17	54 / 100	476 ms	52208 KB

Alice
Bob

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <iostream>
#include <array>
#include <vector>
#define ll long long

using namespace std;

void Alice( int N, int M, int A[], int B[] ){
	vector <array<ll, 2>> V;
	ll k = N, tot = 0, cnt = N;
	while (k) {
		k /= 2;
		++tot;
	}
	for (int i=0; i<M; ++i) {
		V.push_back({A[i], B[i]});
	}
	k = 1;
	V.push_back({cnt, cnt+1});
	++cnt;
	for (int i=0; i<tot; ++i) {
		for (int j=0; j<N; ++j) {
			if ((j+1) & k) V.push_back({cnt, j});
		}
		if (i != tot-1) V.push_back({cnt, cnt+1});
		++cnt, k *= 2;
	}
	for (int i=0; i<cnt; ++i) {
		V.push_back({i, cnt});
	}
	++cnt;
	for (int j=N; j<N+tot+1; ++j) {
		V.push_back({j, cnt});
	}
	++cnt;
	InitG(cnt, V.size());
	int i = 0;
	for (auto [a, b] : V) {
		//cout << a << " " << b << endl;
		MakeG(i++, a, b);
	}
}

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#define ll long long

using namespace std;

ll in[2000], F[2000];
bool B[2000], G[2000];
vector <ll> adj[2000];
vector <array<ll, 2> > V, X;
ll n, x, z, rt = 0;

void dfs(ll u, ll p, ll k) {
	for (auto v : adj[u]) {
		if (!G[v] && v != rt && v != z) {
			F[v] += k;
		}
	}
	for (auto v : adj[u]) {
		if (G[v] && v != p) dfs(v, u, (!k ? 1 : k*2));
	}
}
void Bob( int Z, int U, int C[], int D[] ){
	n = Z;
	V.clear();
	X.clear();
	for (int i=0; i<n; ++i) in[i] = B[i] = F[i] = G[i] = 0, adj[i].clear();
	for (int i=0; i<U; ++i) {
		++in[C[i]], ++in[D[i]];
		adj[C[i]].push_back(D[i]);
		adj[D[i]].push_back(C[i]);
	}
	for (int i=0; i<n; ++i) {
		if (in[i] == n-2) {
			rt = i;
		}
	}
	B[rt] = 1;
	for (auto v : adj[rt]) {
		B[v] = 1;
	}
	z = rt;
	for (int i=0; i<n; ++i) {
		if (!B[i]) {
			rt = i;
			break;
		}
	}
	x = Z-2-adj[rt].size();
	for (auto v : adj[rt]) {
		in[v] -= 2;
		//cout << v << " " << in[v] << endl;
		G[v] = 1;
	}
	for (auto v : adj[rt]) {
		if (in[v] == 1) {
			dfs(v, -1, 0);
			break;
		}
	}
	/*for (int i=0; i<n; ++i) {
		cout << F[i] << " ";
	}
	cout << endl;*/
	for (int i=0; i<U; ++i) {
		if (F[C[i]] && F[D[i]]) {
			//cout << F[C[i]]-1 << " " << F[D[i]]-1 << endl;
			V.push_back({F[C[i]]-1, F[D[i]]-1});
		}
	}
	InitMap(x, V.size());
	for (auto [a, b] : V) {
		MakeMap(a, b);
	}
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:32:46: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   32 |  for (int i=0; i<n; ++i) in[i] = B[i] = F[i] = G[i] = 0, adj[i].clear();
      |                                         ~~~~~^~~~~~~~~~

Subtask #1
0 / 22.0

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

Subtask #2
0 / 15.0

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

Subtask #3
54.0 / 63.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	356 ms	50832 KB	Output is partially correct : V - N = 13
2	Partially correct	308 ms	50444 KB	Output is partially correct : V - N = 13
3	Partially correct	110 ms	27268 KB	Output is partially correct : V - N = 13
4	Partially correct	6 ms	16020 KB	Output is partially correct : V - N = 13
5	Partially correct	69 ms	21400 KB	Output is partially correct : V - N = 13
6	Partially correct	250 ms	48764 KB	Output is partially correct : V - N = 13
7	Partially correct	395 ms	51580 KB	Output is partially correct : V - N = 13
8	Partially correct	326 ms	50324 KB	Output is partially correct : V - N = 13
9	Partially correct	165 ms	29700 KB	Output is partially correct : V - N = 13
10	Partially correct	22 ms	17312 KB	Output is partially correct : V - N = 13
11	Partially correct	33 ms	18844 KB	Output is partially correct : V - N = 13
12	Partially correct	218 ms	35792 KB	Output is partially correct : V - N = 13
13	Partially correct	335 ms	49372 KB	Output is partially correct : V - N = 13
14	Partially correct	376 ms	49876 KB	Output is partially correct : V - N = 13
15	Partially correct	220 ms	41912 KB	Output is partially correct : V - N = 13
16	Partially correct	61 ms	19616 KB	Output is partially correct : V - N = 13
17	Partially correct	18 ms	16772 KB	Output is partially correct : V - N = 13
18	Partially correct	148 ms	27524 KB	Output is partially correct : V - N = 13
19	Partially correct	304 ms	51336 KB	Output is partially correct : V - N = 13
20	Partially correct	356 ms	50496 KB	Output is partially correct : V - N = 13
21	Correct	98 ms	25724 KB	Output is correct : V - N = 12
22	Correct	80 ms	21700 KB	Output is correct : V - N = 12
23	Partially correct	28 ms	18424 KB	Output is partially correct : V - N = 13
24	Partially correct	4 ms	15632 KB	Output is partially correct : V - N = 13
25	Partially correct	20 ms	17404 KB	Output is partially correct : V - N = 13
26	Correct	59 ms	21396 KB	Output is correct : V - N = 12
27	Correct	95 ms	22160 KB	Output is correct : V - N = 12
28	Partially correct	78 ms	21896 KB	Output is partially correct : V - N = 13
29	Partially correct	44 ms	18860 KB	Output is partially correct : V - N = 13
30	Correct	6 ms	16264 KB	Output is correct : V - N = 12
31	Partially correct	6 ms	14096 KB	Output is partially correct : V - N = 13
32	Partially correct	7 ms	14028 KB	Output is partially correct : V - N = 13
33	Partially correct	6 ms	14096 KB	Output is partially correct : V - N = 13
34	Partially correct	7 ms	14016 KB	Output is partially correct : V - N = 13
35	Partially correct	6 ms	14096 KB	Output is partially correct : V - N = 13
36	Partially correct	360 ms	51092 KB	Output is partially correct : V - N = 13
37	Partially correct	396 ms	52208 KB	Output is partially correct : V - N = 13
38	Partially correct	364 ms	51696 KB	Output is partially correct : V - N = 13
39	Partially correct	402 ms	50544 KB	Output is partially correct : V - N = 13
40	Partially correct	364 ms	51264 KB	Output is partially correct : V - N = 13
41	Partially correct	64 ms	21392 KB	Output is partially correct : V - N = 13
42	Partially correct	49 ms	19860 KB	Output is partially correct : V - N = 13
43	Partially correct	56 ms	21152 KB	Output is partially correct : V - N = 13
44	Partially correct	5 ms	16140 KB	Output is partially correct : V - N = 13
45	Partially correct	30 ms	19100 KB	Output is partially correct : V - N = 13
46	Partially correct	147 ms	29580 KB	Output is partially correct : V - N = 13
47	Partially correct	66 ms	21396 KB	Output is partially correct : V - N = 13
48	Partially correct	162 ms	29588 KB	Output is partially correct : V - N = 13
49	Partially correct	34 ms	18340 KB	Output is partially correct : V - N = 13
50	Partially correct	10 ms	16780 KB	Output is partially correct : V - N = 13
51	Partially correct	309 ms	48820 KB	Output is partially correct : V - N = 13
52	Partially correct	6 ms	16012 KB	Output is partially correct : V - N = 13
53	Partially correct	235 ms	48080 KB	Output is partially correct : V - N = 13
54	Partially correct	320 ms	50724 KB	Output is partially correct : V - N = 13
55	Partially correct	24 ms	17092 KB	Output is partially correct : V - N = 13
56	Partially correct	203 ms	34996 KB	Output is partially correct : V - N = 13
57	Partially correct	476 ms	50800 KB	Output is partially correct : V - N = 13
58	Partially correct	46 ms	19428 KB	Output is partially correct : V - N = 13
59	Partially correct	157 ms	29256 KB	Output is partially correct : V - N = 13
60	Partially correct	369 ms	50720 KB	Output is partially correct : V - N = 13
61	Correct	2 ms	15616 KB	Output is correct : V - N = 9
62	Correct	3 ms	15628 KB	Output is correct : V - N = 9
63	Correct	3 ms	15620 KB	Output is correct : V - N = 9
64	Correct	2 ms	15620 KB	Output is correct : V - N = 9
65	Correct	2 ms	15620 KB	Output is correct : V - N = 9
66	Correct	3 ms	15616 KB	Output is correct : V - N = 9
67	Correct	2 ms	15620 KB	Output is correct : V - N = 9
68	Correct	3 ms	15620 KB	Output is correct : V - N = 9
69	Correct	2 ms	15620 KB	Output is correct : V - N = 9
70	Correct	1 ms	15620 KB	Output is correct : V - N = 9
71	Correct	3 ms	15620 KB	Output is correct : V - N = 9
72	Correct	2 ms	15616 KB	Output is correct : V - N = 9
73	Correct	2 ms	15620 KB	Output is correct : V - N = 9
74	Correct	3 ms	15628 KB	Output is correct : V - N = 9
75	Correct	3 ms	15628 KB	Output is correct : V - N = 9
76	Correct	1 ms	15620 KB	Output is correct : V - N = 9
77	Correct	2 ms	15620 KB	Output is correct : V - N = 9
78	Correct	3 ms	15628 KB	Output is correct : V - N = 9
79	Correct	3 ms	15868 KB	Output is correct : V - N = 9
80	Correct	3 ms	15616 KB	Output is correct : V - N = 9
81	Correct	3 ms	15620 KB	Output is correct : V - N = 8
82	Correct	2 ms	15628 KB	Output is correct : V - N = 8
83	Correct	3 ms	15620 KB	Output is correct : V - N = 9
84	Correct	3 ms	15620 KB	Output is correct : V - N = 9
85	Correct	2 ms	15616 KB	Output is correct : V - N = 9
86	Correct	2 ms	15624 KB	Output is correct : V - N = 9
87	Correct	3 ms	15628 KB	Output is correct : V - N = 9
88	Correct	2 ms	15616 KB	Output is correct : V - N = 9
89	Correct	2 ms	15620 KB	Output is correct : V - N = 9
90	Correct	3 ms	15620 KB	Output is correct : V - N = 9
91	Correct	1 ms	13580 KB	Output is correct : V - N = 9
92	Correct	2 ms	13572 KB	Output is correct : V - N = 9
93	Correct	2 ms	13572 KB	Output is correct : V - N = 9
94	Correct	2 ms	13572 KB	Output is correct : V - N = 9
95	Correct	2 ms	13568 KB	Output is correct : V - N = 9
96	Correct	3 ms	15632 KB	Output is correct : V - N = 9
97	Correct	3 ms	15636 KB	Output is correct : V - N = 9
98	Correct	3 ms	15616 KB	Output is correct : V - N = 9
99	Correct	3 ms	15620 KB	Output is correct : V - N = 9
100	Correct	2 ms	15616 KB	Output is correct : V - N = 9
101	Correct	3 ms	15616 KB	Output is correct : V - N = 9
102	Correct	3 ms	15620 KB	Output is correct : V - N = 9
103	Correct	3 ms	15620 KB	Output is correct : V - N = 9
104	Correct	2 ms	13568 KB	Output is correct : V - N = 9
105	Correct	2 ms	15628 KB	Output is correct : V - N = 9
106	Correct	3 ms	15620 KB	Output is correct : V - N = 9
107	Correct	3 ms	15616 KB	Output is correct : V - N = 9
108	Correct	3 ms	15628 KB	Output is correct : V - N = 9
109	Correct	2 ms	15616 KB	Output is correct : V - N = 9
110	Correct	2 ms	15620 KB	Output is correct : V - N = 9
111	Correct	3 ms	15620 KB	Output is correct : V - N = 9
112	Correct	2 ms	15620 KB	Output is correct : V - N = 8
113	Correct	2 ms	15620 KB	Output is correct : V - N = 8
114	Correct	3 ms	15616 KB	Output is correct : V - N = 8
115	Correct	2 ms	15616 KB	Output is correct : V - N = 8
116	Correct	2 ms	15620 KB	Output is correct : V - N = 8
117	Correct	3 ms	15616 KB	Output is correct : V - N = 9
118	Correct	2 ms	15620 KB	Output is correct : V - N = 8
119	Correct	2 ms	15684 KB	Output is correct : V - N = 9
120	Correct	3 ms	15620 KB	Output is correct : V - N = 8
121	Correct	1 ms	15616 KB	Output is correct : V - N = 7
122	Correct	3 ms	15620 KB	Output is correct : V - N = 7
123	Correct	1 ms	15628 KB	Output is correct : V - N = 7
124	Correct	2 ms	13568 KB	Output is correct : V - N = 7
125	Correct	2 ms	15620 KB	Output is correct : V - N = 7
126	Correct	1 ms	15628 KB	Output is correct : V - N = 7
127	Correct	2 ms	15620 KB	Output is correct : V - N = 7
128	Correct	3 ms	15620 KB	Output is correct : V - N = 7
129	Correct	2 ms	15628 KB	Output is correct : V - N = 7
130	Correct	2 ms	13580 KB	Output is correct : V - N = 7
131	Correct	1 ms	15624 KB	Output is correct : V - N = 7
132	Correct	2 ms	15708 KB	Output is correct : V - N = 7
133	Correct	2 ms	15620 KB	Output is correct : V - N = 7
134	Correct	2 ms	15620 KB	Output is correct : V - N = 7
135	Correct	1 ms	15616 KB	Output is correct : V - N = 7
136	Correct	1 ms	15620 KB	Output is correct : V - N = 7
137	Correct	2 ms	15620 KB	Output is correct : V - N = 7
138	Correct	1 ms	15616 KB	Output is correct : V - N = 7
139	Correct	2 ms	15620 KB	Output is correct : V - N = 7
140	Correct	2 ms	15616 KB	Output is correct : V - N = 7
141	Correct	2 ms	15628 KB	Output is correct : V - N = 7
142	Correct	2 ms	15620 KB	Output is correct : V - N = 7
143	Correct	1 ms	15628 KB	Output is correct : V - N = 7
144	Correct	2 ms	13564 KB	Output is correct : V - N = 6
145	Correct	1 ms	15620 KB	Output is correct : V - N = 6
146	Correct	2 ms	15620 KB	Output is correct : V - N = 6
147	Correct	1 ms	15620 KB	Output is correct : V - N = 6
148	Correct	2 ms	15688 KB	Output is correct : V - N = 7
149	Correct	1 ms	15620 KB	Output is correct : V - N = 7
150	Correct	1 ms	13572 KB	Output is correct : V - N = 7
151	Correct	2 ms	13572 KB	Output is correct : V - N = 7
152	Correct	1 ms	13576 KB	Output is correct : V - N = 7
153	Correct	2 ms	13572 KB	Output is correct : V - N = 7
154	Correct	1 ms	13572 KB	Output is correct : V - N = 7
155	Correct	1 ms	13572 KB	Output is correct : V - N = 7
156	Correct	3 ms	15616 KB	Output is correct : V - N = 7
157	Correct	3 ms	15620 KB	Output is correct : V - N = 7
158	Correct	1 ms	15628 KB	Output is correct : V - N = 7
159	Correct	2 ms	15628 KB	Output is correct : V - N = 7
160	Correct	1 ms	15628 KB	Output is correct : V - N = 7
161	Correct	1 ms	15628 KB	Output is correct : V - N = 7
162	Correct	2 ms	15620 KB	Output is correct : V - N = 7
163	Correct	1 ms	15620 KB	Output is correct : V - N = 7
164	Correct	1 ms	13572 KB	Output is correct : V - N = 7
165	Correct	2 ms	13572 KB	Output is correct : V - N = 7
166	Correct	2 ms	15628 KB	Output is correct : V - N = 7
167	Correct	2 ms	15620 KB	Output is correct : V - N = 7
168	Correct	2 ms	15620 KB	Output is correct : V - N = 7
169	Correct	2 ms	15620 KB	Output is correct : V - N = 7
170	Correct	1 ms	13572 KB	Output is correct : V - N = 7
171	Correct	2 ms	13572 KB	Output is correct : V - N = 4
172	Correct	2 ms	15632 KB	Output is correct : V - N = 5
173	Correct	2 ms	13572 KB	Output is correct : V - N = 5
174	Correct	1 ms	15620 KB	Output is correct : V - N = 5
175	Correct	2 ms	15620 KB	Output is correct : V - N = 5
176	Correct	2 ms	15620 KB	Output is correct : V - N = 6
177	Correct	2 ms	15620 KB	Output is correct : V - N = 6
178	Correct	2 ms	15628 KB	Output is correct : V - N = 6

Submission #1071442

Compilation message

Subtask #1 0 / 22.0

Subtask #2 0 / 15.0

Subtask #3 54.0 / 63.0

Subtask #1
0 / 22.0

Subtask #2
0 / 15.0

Subtask #3
54.0 / 63.0