oj.uz

Submission #648774

# Submission time Handle Problem Language Result Execution time Memory
648774 2022-10-08T08:51:53 Z Johann Airline Route Map (JOI18_airline) C++14
0 / 100
 822 ms 21332 KB 
#include "Alicelib.h"
#include <cassert>
#include <cstdio>

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

typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()

void Alice(int N, int M, int A[], int B[])
{
	vpii edges;
	// von Z := N + 10 zu allen Knoten von G
	for (int i = 0; i < N; ++i)
		edges.push_back({N + 10, i});
	// von C := N + 11 zu allen Kontrolknoten
	for (int i = 0; i < 11; ++i)
		edges.push_back({N + 11, N + i});
	// Zwischen den Count Bits (der letzte zu Z)
	for (int b = 0; b < 10; ++b)
		edges.push_back({N + b, N + b + 1});
	// für alle anderen Knoten im Graph:
	for (int v = 0; v < N; ++v)
		for (int b = 0; b < 10; ++b)
			if (v & (1 << b))
				edges.push_back({v, N + b});
	// Ausfüllen
	InitG(N + 12, M + sz(edges));
	int idx = 0;
	for (int i = 0; i < M; ++i)
		MakeG(idx++, A[i], B[i]);
	for (pii e : edges)
		MakeG(idx++, e.first, e.second);
}

#include "Boblib.h"
#include <cassert>
#include <cstdio>

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

typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
#define sz(x) (int)(x).size()

void dfs(vvi &adj, int v, vi &countBits, vi &rename)
{
	rename[v] = -2;
	for (int u : adj[v])
	{
		if (rename[u] != -1)
			continue;
		dfs(adj, u, countBits, rename);
	}
	countBits.push_back(v);
}

void Bob(int V, int U, int C[], int D[])
{
	vvi adj(V);
	for (int i = 0; i < U; ++i)
		adj[C[i]].push_back(D[i]), adj[D[i]].push_back(C[i]);

	bool poss = false;
	int c = -1, z = -1;
	for (int cc = 0; cc < V; ++cc)
	{
		if (sz(adj[cc]) != 11)
			continue;
		for (int cz : adj[cc])
		{
			if (sz(adj[cz]) != V - 10)
				continue;
			vb nodes(V, false);
			for (int x : adj[cz])
				nodes[x] = true;
			for (int x : adj[cc])
				nodes[x] = true;
			poss = true;
			for (bool x : nodes)
				if (!x)
					poss = false;
			if (poss)
			{
				c = cc;
				z = cz;
			}
		}
		if (poss)
			break;
	}
	vi rename(V, 0);
	rename[c] = -2;
	for (int x : adj[c])
		rename[x] = -1;
	vi countBits;
	dfs(adj, z, countBits, rename);

	for (int b = 0; b < 10; ++b)
	{
		for (int v : adj[countBits[b]])
			if (rename[v] >= 0)
				rename[v] += (1 << b);
	}

	int M = 0;
	for (int v = 0; v < V; ++v)
		// Alle Kanten zwischen den Kontrollknoten und den Normalen werden enternt
		M += sz(adj[v]) * ((rename[v] >= 0) ? 1 : -1);
	M /= 2;
	M += 21; // Kanten zwischen den Knotrollknoten, müssen noch addiert werden.
	InitMap(V - 12, M);
	for (int v = 0; v < V; ++v)
	{
		if (rename[v] < 0)
			continue;
		for (int u : adj[v])
			if (rename[u] >= 0 && rename[v] > rename[u])
				MakeMap(rename[v], rename[u]);
	}
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4516 KB Output is correct
2 Correct 3 ms 4612 KB Output is correct
3 Correct 3 ms 4612 KB Output is correct
4 Correct 3 ms 4620 KB Output is correct
5 Correct 3 ms 4612 KB Output is correct
6 Correct 2 ms 4612 KB Output is correct
7 Correct 3 ms 4596 KB Output is correct
8 Correct 3 ms 4536 KB Output is correct
9 Correct 3 ms 4596 KB Output is correct
10 Correct 3 ms 4608 KB Output is correct
11 Correct 3 ms 4612 KB Output is correct
12 Correct 3 ms 4588 KB Output is correct
13 Correct 2 ms 4592 KB Output is correct
14 Correct 3 ms 4612 KB Output is correct
15 Correct 3 ms 4612 KB Output is correct
16 Correct 3 ms 4588 KB Output is correct
17 Correct 3 ms 4596 KB Output is correct
18 Correct 3 ms 4616 KB Output is correct
19 Correct 2 ms 4612 KB Output is correct
20 Correct 3 ms 4588 KB Output is correct
21 Correct 3 ms 4588 KB Output is correct
22 Correct 3 ms 4612 KB Output is correct
23 Correct 3 ms 4664 KB Output is correct
24 Correct 3 ms 4548 KB Output is correct
25 Correct 3 ms 4612 KB Output is correct
26 Correct 3 ms 4612 KB Output is correct
27 Correct 3 ms 4552 KB Output is correct
28 Runtime error 4 ms 5768 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4516 KB Output is correct
2 Correct 3 ms 4612 KB Output is correct
3 Correct 3 ms 4612 KB Output is correct
4 Correct 3 ms 4620 KB Output is correct
5 Correct 3 ms 4612 KB Output is correct
6 Correct 2 ms 4612 KB Output is correct
7 Correct 3 ms 4596 KB Output is correct
8 Correct 3 ms 4536 KB Output is correct
9 Correct 3 ms 4596 KB Output is correct
10 Correct 3 ms 4608 KB Output is correct
11 Correct 3 ms 4612 KB Output is correct
12 Correct 3 ms 4588 KB Output is correct
13 Correct 2 ms 4592 KB Output is correct
14 Correct 3 ms 4612 KB Output is correct
15 Correct 3 ms 4612 KB Output is correct
16 Correct 3 ms 4588 KB Output is correct
17 Correct 3 ms 4596 KB Output is correct
18 Correct 3 ms 4616 KB Output is correct
19 Correct 2 ms 4612 KB Output is correct
20 Correct 3 ms 4588 KB Output is correct
21 Correct 3 ms 4588 KB Output is correct
22 Correct 3 ms 4612 KB Output is correct
23 Correct 3 ms 4664 KB Output is correct
24 Correct 3 ms 4548 KB Output is correct
25 Correct 3 ms 4612 KB Output is correct
26 Correct 3 ms 4612 KB Output is correct
27 Correct 3 ms 4552 KB Output is correct
28 Runtime error 4 ms 5768 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 21200 KB Output is correct : V - N = 12
2 Correct 552 ms 18384 KB Output is correct : V - N = 12
3 Correct 161 ms 10532 KB Output is correct : V - N = 12
4 Correct 10 ms 5104 KB Output is correct : V - N = 12
5 Correct 112 ms 8192 KB Output is correct : V - N = 12
6 Correct 417 ms 16876 KB Output is correct : V - N = 12
7 Correct 620 ms 20920 KB Output is correct : V - N = 12
8 Correct 562 ms 19740 KB Output is correct : V - N = 12
9 Correct 276 ms 12408 KB Output is correct : V - N = 12
10 Correct 30 ms 5828 KB Output is correct : V - N = 12
11 Correct 65 ms 6468 KB Output is correct : V - N = 12
12 Correct 370 ms 14032 KB Output is correct : V - N = 12
13 Correct 683 ms 20392 KB Output is correct : V - N = 12
14 Correct 735 ms 20568 KB Output is correct : V - N = 12
15 Correct 309 ms 15980 KB Output is correct : V - N = 12
16 Correct 67 ms 7292 KB Output is correct : V - N = 12
17 Correct 24 ms 5516 KB Output is correct : V - N = 12
18 Correct 210 ms 11380 KB Output is correct : V - N = 12
19 Correct 553 ms 19244 KB Output is correct : V - N = 12
20 Correct 675 ms 21084 KB Output is correct : V - N = 12
21 Correct 217 ms 10092 KB Output is correct : V - N = 12
22 Correct 108 ms 8348 KB Output is correct : V - N = 12
23 Correct 62 ms 6256 KB Output is correct : V - N = 12
24 Correct 4 ms 4868 KB Output is correct : V - N = 12
25 Correct 31 ms 5724 KB Output is correct : V - N = 12
26 Correct 97 ms 7964 KB Output is correct : V - N = 12
27 Correct 175 ms 9024 KB Output is correct : V - N = 12
28 Correct 122 ms 8800 KB Output is correct : V - N = 12
29 Correct 63 ms 6756 KB Output is correct : V - N = 12
30 Correct 13 ms 5136 KB Output is correct : V - N = 12
31 Correct 7 ms 4992 KB Output is correct : V - N = 12
32 Correct 7 ms 4924 KB Output is correct : V - N = 12
33 Correct 8 ms 4992 KB Output is correct : V - N = 12
34 Correct 8 ms 4896 KB Output is correct : V - N = 12
35 Correct 8 ms 4992 KB Output is correct : V - N = 12
36 Correct 641 ms 21332 KB Output is correct : V - N = 12
37 Correct 695 ms 21088 KB Output is correct : V - N = 12
38 Correct 778 ms 21124 KB Output is correct : V - N = 12
39 Correct 747 ms 21064 KB Output is correct : V - N = 12
40 Correct 687 ms 21160 KB Output is correct : V - N = 12
41 Correct 145 ms 8048 KB Output is correct : V - N = 12
42 Correct 127 ms 7532 KB Output is correct : V - N = 12
43 Correct 117 ms 8088 KB Output is correct : V - N = 12
44 Correct 9 ms 5064 KB Output is correct : V - N = 12
45 Correct 56 ms 6648 KB Output is correct : V - N = 12
46 Correct 237 ms 10904 KB Output is correct : V - N = 12
47 Correct 103 ms 8028 KB Output is correct : V - N = 12
48 Correct 334 ms 12324 KB Output is correct : V - N = 12
49 Correct 46 ms 6408 KB Output is correct : V - N = 12
50 Correct 24 ms 5492 KB Output is correct : V - N = 12
51 Correct 416 ms 18472 KB Output is correct : V - N = 12
52 Correct 7 ms 5104 KB Output is correct : V - N = 12
53 Correct 387 ms 16928 KB Output is correct : V - N = 12
54 Correct 610 ms 19336 KB Output is correct : V - N = 12
55 Correct 27 ms 5792 KB Output is correct : V - N = 12
56 Correct 305 ms 13576 KB Output is correct : V - N = 12
57 Correct 601 ms 20436 KB Output is correct : V - N = 12
58 Correct 99 ms 7244 KB Output is correct : V - N = 12
59 Correct 252 ms 11432 KB Output is correct : V - N = 12
60 Correct 822 ms 20532 KB Output is correct : V - N = 12
61 Correct 3 ms 4540 KB Output is correct : V - N = 12
62 Correct 3 ms 4612 KB Output is correct : V - N = 12
63 Correct 3 ms 4620 KB Output is correct : V - N = 12
64 Correct 3 ms 4608 KB Output is correct : V - N = 12
65 Correct 3 ms 4592 KB Output is correct : V - N = 12
66 Correct 3 ms 4612 KB Output is correct : V - N = 12
67 Correct 3 ms 4616 KB Output is correct : V - N = 12
68 Correct 3 ms 4588 KB Output is correct : V - N = 12
69 Correct 3 ms 4608 KB Output is correct : V - N = 12
70 Correct 3 ms 4616 KB Output is correct : V - N = 12
71 Correct 3 ms 4616 KB Output is correct : V - N = 12
72 Correct 3 ms 4540 KB Output is correct : V - N = 12
73 Correct 3 ms 4612 KB Output is correct : V - N = 12
74 Correct 3 ms 4708 KB Output is correct : V - N = 12
75 Correct 3 ms 4624 KB Output is correct : V - N = 12
76 Correct 3 ms 4612 KB Output is correct : V - N = 12
77 Correct 3 ms 4620 KB Output is correct : V - N = 12
78 Correct 3 ms 4592 KB Output is correct : V - N = 12
79 Correct 3 ms 4612 KB Output is correct : V - N = 12
80 Correct 3 ms 4612 KB Output is correct : V - N = 12
81 Correct 3 ms 4612 KB Output is correct : V - N = 12
82 Correct 3 ms 4620 KB Output is correct : V - N = 12
83 Correct 3 ms 4604 KB Output is correct : V - N = 12
84 Correct 3 ms 4592 KB Output is correct : V - N = 12
85 Correct 3 ms 4616 KB Output is correct : V - N = 12
86 Correct 3 ms 4612 KB Output is correct : V - N = 12
87 Correct 3 ms 4612 KB Output is correct : V - N = 12
88 Correct 3 ms 4612 KB Output is correct : V - N = 12
89 Correct 3 ms 4616 KB Output is correct : V - N = 12
90 Correct 3 ms 4528 KB Output is correct : V - N = 12
91 Correct 3 ms 4608 KB Output is correct : V - N = 12
92 Correct 3 ms 4624 KB Output is correct : V - N = 12
93 Correct 3 ms 4612 KB Output is correct : V - N = 12
94 Correct 3 ms 4608 KB Output is correct : V - N = 12
95 Correct 3 ms 4608 KB Output is correct : V - N = 12
96 Correct 3 ms 4748 KB Output is correct : V - N = 12
97 Correct 3 ms 4748 KB Output is correct : V - N = 12
98 Correct 3 ms 4612 KB Output is correct : V - N = 12
99 Correct 3 ms 4624 KB Output is correct : V - N = 12
100 Correct 3 ms 4548 KB Output is correct : V - N = 12
101 Correct 3 ms 4612 KB Output is correct : V - N = 12
102 Correct 3 ms 4612 KB Output is correct : V - N = 12
103 Correct 3 ms 4612 KB Output is correct : V - N = 12
104 Correct 3 ms 4608 KB Output is correct : V - N = 12
105 Correct 3 ms 4592 KB Output is correct : V - N = 12
106 Correct 3 ms 4612 KB Output is correct : V - N = 12
107 Correct 3 ms 4612 KB Output is correct : V - N = 12
108 Correct 3 ms 4612 KB Output is correct : V - N = 12
109 Correct 3 ms 4612 KB Output is correct : V - N = 12
110 Correct 3 ms 4552 KB Output is correct : V - N = 12
111 Correct 3 ms 4620 KB Output is correct : V - N = 12
112 Correct 3 ms 4700 KB Output is correct : V - N = 12
113 Correct 3 ms 4620 KB Output is correct : V - N = 12
114 Correct 3 ms 4620 KB Output is correct : V - N = 12
115 Correct 3 ms 4612 KB Output is correct : V - N = 12
116 Correct 3 ms 4612 KB Output is correct : V - N = 12
117 Correct 3 ms 4612 KB Output is correct : V - N = 12
118 Correct 3 ms 4588 KB Output is correct : V - N = 12
119 Correct 3 ms 4540 KB Output is correct : V - N = 12
120 Correct 3 ms 4612 KB Output is correct : V - N = 12
121 Correct 3 ms 4620 KB Output is correct : V - N = 12
122 Correct 3 ms 4612 KB Output is correct : V - N = 12
123 Correct 3 ms 4616 KB Output is correct : V - N = 12
124 Correct 3 ms 4608 KB Output is correct : V - N = 12
125 Correct 3 ms 4616 KB Output is correct : V - N = 12
126 Correct 3 ms 4620 KB Output is correct : V - N = 12
127 Correct 3 ms 4612 KB Output is correct : V - N = 12
128 Correct 3 ms 4616 KB Output is correct : V - N = 12
129 Correct 3 ms 4612 KB Output is correct : V - N = 12
130 Correct 3 ms 4528 KB Output is correct : V - N = 12
131 Correct 3 ms 4612 KB Output is correct : V - N = 12
132 Correct 3 ms 4612 KB Output is correct : V - N = 12
133 Correct 3 ms 4612 KB Output is correct : V - N = 12
134 Correct 3 ms 4520 KB Output is correct : V - N = 12
135 Correct 3 ms 4624 KB Output is correct : V - N = 12
136 Correct 2 ms 4612 KB Output is correct : V - N = 12
137 Correct 3 ms 4596 KB Output is correct : V - N = 12
138 Correct 3 ms 4612 KB Output is correct : V - N = 12
139 Correct 3 ms 4592 KB Output is correct : V - N = 12
140 Correct 3 ms 4612 KB Output is correct : V - N = 12
141 Correct 3 ms 4612 KB Output is correct : V - N = 12
142 Correct 3 ms 4612 KB Output is correct : V - N = 12
143 Correct 2 ms 4612 KB Output is correct : V - N = 12
144 Correct 2 ms 4608 KB Output is correct : V - N = 12
145 Correct 3 ms 4612 KB Output is correct : V - N = 12
146 Correct 3 ms 4612 KB Output is correct : V - N = 12
147 Correct 3 ms 4608 KB Output is correct : V - N = 12
148 Runtime error 4 ms 5744 KB Execution killed with signal 11
149 Halted 0 ms 0 KB -