PaintItBlack

SRM 782 · 2020-03-26 · by jy_25

SRM 782 · 2020-03-26 · by jy_25 · Graph Theory

Show categories

Class Name: PaintItBlack

Return Type: int[]

Method Name: findWalk

Arg Types: (int, int, vector<int>, vector<int>)

Problem Statement

You are given an undirected connected simple graph with n nodes, numbered 0, 1, ..., n-1. The edges of the graph are given in the int[]s a and b: for each valid i, there is an undirected edge between a[i] and b[i].

You are currently in the vertex u and all the vertices are colored white. Whenever you go from some vertex p to some vertex q, you must toggle the color of q (from white to black and vice versa). Note that p's color remains unchanged.

Find whether there is a closed walk (starting and ending at u) with less than or equal to 5 * n moves which will leave all the vertices colored black. (Note that each edge can be traversed any number of times in both directions.)

If there is a solution, return a int[] describing one solution by listing the order in which it visits nodes (including u both at the beginning and at the end). Otherwise, return an empty int[].

Notes

You do not have to minimize the length of the returned walk.

Constraints

n will be between 2 and 200 inclusive.
u will be between 0 and n - 1 inclusive.
a will have between n - 1 and 1000 elements inclusive.
a and b will have the same number of elements.
Every element of a and b will be between 0 and n - 1 inclusive.
The graph described by n, a, b will be a simple undirected connected graph.

Examples

2
0
{0}
{1}
Returns: {0, 1, 0 }

3
0
{0, 1}
{1, 2}
Returns: { }

4
2
{0, 1, 2, 3}
{1, 2, 3, 0}
Returns: {2, 3, 0, 1, 2 }

172
15
{94, 30, 164, 12, 71, 14, 37, 15, 131, 93, 143, 115, 57, 5, 87, 58, 121, 139, 8, 65, 138, 125, 85, 40, 162, 69, 43, 142, 0, 38, 161, 152, 91, 168, 107, 27, 54, 170, 3, 151, 84, 1, 153, 123, 61, 113, 19, 98, 110, 42, 7, 130, 70, 86, 62, 148, 31, 16, 29, 17, 55, 26, 76, 119, 49, 21, 158, 136, 90, 140, 134, 60, 169, 51, 155, 46, 165, 109, 127, 10, 97, 9, 4, 104, 52, 120, 88, 11, 102, 35, 83, 63, 39, 32, 72, 129, 2, 149, 111, 33, 99, 126, 144, 118, 157, 117, 96, 159, 163, 156, 124, 28, 133, 45, 18, 132, 116, 64, 66, 50, 24, 53, 103, 20, 78, 100, 146, 141, 89, 81, 92, 67, 150, 160, 68, 74, 135, 105, 145, 167, 77, 44, 13, 25, 114, 128, 171, 48, 23, 6, 41, 75, 106, 112, 166, 108, 80, 154, 82, 34, 59, 79, 56, 95, 137, 73, 147, 122, 101, 47, 22, 166, 81, 115, 22, 38, 5, 112, 34, 159, 151, 53, 149, 5, 135, 143, 1, 166, 22, 23, 136, 123, 34, 138, 171, 105, 110, 41, 37, 68, 136, 48, 116, 111, 50, 119, 110, 118, 153, 115, 49, 167, 163, 0, 148, 59, 109, 0, 7, 57, 42, 65, 52, 157, 45, 0, 26, 9, 164, 120, 56, 3, 119, 171, 109, 106, 83, 118, 62, 71, 93, 41, 126, 145, 85, 55, 146, 18, 68, 106, 156, 108, 38, 167, 141, 20, 28, 53, 105, 63, 52, 69, 171, 50, 117, 135, 139, 70, 79, 104, 39, 87, 82, 142, 31, 99, 23, 24, 99, 113, 78, 57, 133, 145, 38, 145, 73, 97, 57, 80, 24, 30, 43, 65, 56, 113, 22, 116, 126, 75, 115, 148, 64, 155, 168, 102, 16, 77, 4, 130, 164, 162, 115, 100, 155, 154, 71, 164, 117, 54, 101, 53, 128, 50, 19, 42, 100, 169, 42, 61, 23, 11, 120, 116, 89, 117, 55, 32, 73, 36, 99, 14, 154, 90, 155, 116, 100, 12, 39, 52, 91, 159, 69, 0, 129, 76, 60, 15, 134, 110, 125, 82, 140, 121, 35, 93, 58, 29, 70, 18, 156, 72, 69, 54, 19, 142, 122, 80, 133, 32, 148, 135, 56, 7, 123, 129, 2, 160, 137, 119, 100, 49, 1, 67, 8, 64, 100, 162, 33, 135, 100, 146, 94, 62, 78, 44, 135, 63, 167, 29, 154, 48, 104, 13, 60, 159, 108, 90, 139, 64, 78, 95, 9, 83, 121, 124, 151, 170, 123, 6, 23, 118, 159, 120, 162, 115, 75, 66, 116, 54, 164, 3, 9, 82, 20, 73, 28, 101, 57, 67, 47, 107, 132, 100, 147, 68, 144, 16, 28, 8, 63, 152, 80, 37, 144, 171, 40, 127, 159, 133, 122, 22, 54, 82, 158, 99, 158, 140, 160, 123, 130, 48, 102, 37, 35, 127, 38, 133, 2, 100, 136, 164, 6, 39, 60, 53, 108, 38, 50}
{36, 36, 36, 164, 164, 94, 14, 30, 164, 131, 93, 37, 71, 37, 12, 115, 30, 58, 139, 5, 12, 58, 131, 164, 115, 138, 143, 5, 121, 37, 143, 36, 8, 115, 164, 168, 125, 94, 164, 8, 139, 15, 152, 85, 8, 57, 113, 94, 113, 38, 94, 161, 65, 70, 71, 107, 71, 161, 8, 87, 162, 107, 62, 36, 15, 151, 3, 107, 70, 36, 27, 38, 27, 3, 107, 115, 143, 12, 69, 3, 110, 165, 130, 91, 153, 85, 84, 57, 62, 110, 140, 120, 98, 148, 102, 121, 32, 104, 70, 125, 164, 84, 5, 2, 168, 3, 148, 97, 136, 96, 71, 125, 27, 165, 12, 40, 4, 107, 156, 86, 65, 156, 27, 15, 63, 70, 93, 165, 161, 27, 46, 115, 89, 116, 98, 69, 16, 103, 17, 88, 18, 170, 164, 63, 83, 3, 14, 20, 146, 119, 53, 107, 3, 162, 171, 88, 58, 63, 162, 17, 21, 87, 153, 30, 19, 32, 23, 147, 6, 160, 84, 86, 49, 0, 63, 168, 56, 169, 59, 18, 72, 125, 14, 88, 23, 60, 121, 95, 60, 41, 68, 1, 96, 126, 104, 140, 73, 91, 7, 107, 148, 27, 101, 35, 160, 160, 42, 128, 25, 84, 111, 78, 83, 143, 58, 123, 15, 33, 31, 18, 0, 11, 46, 120, 36, 96, 45, 113, 93, 81, 13, 126, 111, 116, 125, 51, 20, 68, 105, 32, 7, 75, 163, 138, 1, 163, 154, 102, 89, 80, 8, 141, 56, 161, 80, 131, 165, 65, 158, 74, 88, 121, 70, 118, 37, 30, 11, 33, 155, 31, 162, 105, 168, 133, 124, 126, 28, 51, 47, 165, 68, 60, 152, 51, 109, 148, 108, 34, 19, 163, 76, 141, 42, 75, 105, 87, 126, 60, 137, 64, 34, 118, 134, 157, 78, 45, 8, 66, 89, 125, 75, 70, 7, 59, 1, 74, 11, 141, 159, 40, 13, 11, 107, 71, 76, 125, 133, 39, 132, 135, 9, 155, 13, 70, 116, 123, 46, 126, 162, 133, 71, 152, 128, 154, 31, 120, 109, 127, 110, 15, 56, 110, 106, 12, 75, 50, 97, 78, 111, 149, 131, 61, 89, 93, 71, 90, 44, 39, 15, 55, 141, 97, 97, 165, 58, 99, 161, 105, 120, 144, 153, 156, 138, 87, 46, 118, 19, 107, 24, 126, 158, 58, 80, 133, 116, 108, 152, 38, 80, 59, 26, 142, 95, 46, 60, 162, 75, 118, 125, 128, 8, 42, 18, 123, 171, 23, 27, 77, 114, 43, 1, 125, 155, 105, 42, 77, 17, 9, 100, 65, 119, 92, 62, 143, 4, 41, 137, 128, 32, 94, 57, 134, 161, 96, 117, 67, 143, 138, 103, 166, 19, 92, 93, 89, 117, 115, 153, 26, 170, 71, 138, 79, 145, 124, 7, 6, 2, 60, 10, 61, 30, 34, 45, 73, 126, 65, 54, 151, 78, 45, 56, 117, 76, 57, 114, 79, 161, 10, 153, 147, 32, 161, 13, 90, 169, 114, 63, 16, 131}
Returns: {15, 1, 78, 60, 22, 34, 17, 87, 7, 31, 71, 8, 16, 26, 45, 36, 30, 95, 94, 14, 37, 5, 56, 13, 6, 65, 11, 53, 41, 23, 9, 113, 19, 2, 32, 73, 67, 115, 0, 12, 18, 55, 46, 52, 88, 84, 126, 3, 10, 133, 27, 48, 20, 83, 105, 62, 76, 24, 51, 106, 69, 74, 63, 25, 153, 144, 153, 148, 58, 44, 162, 4, 89, 68, 98, 39, 29, 128, 66, 77, 90, 70, 33, 80, 141, 108, 64, 43, 42, 38, 109, 100, 59, 21, 151, 72, 97, 110, 35, 111, 49, 81, 120, 85, 123, 117, 147, 122, 161, 130, 125, 28, 143, 93, 121, 129, 75, 107, 92, 118, 50, 86, 166, 171, 104, 91, 104, 149, 104, 171, 116, 101, 138, 145, 138, 101, 138, 101, 116, 160, 47, 99, 142, 146, 154, 146, 142, 146, 142, 99, 164, 40, 54, 158, 54, 165, 54, 40, 132, 40, 164, 57, 103, 57, 164, 57, 164, 131, 164, 99, 47, 160, 47, 160, 119, 160, 116, 160, 116, 171, 116, 171, 166, 171, 166, 86, 50, 86, 50, 118, 92, 118, 92, 107, 136, 163, 136, 107, 136, 107, 155, 79, 127, 79, 152, 79, 155, 157, 168, 82, 61, 135, 156, 96, 156, 135, 156, 135, 61, 82, 61, 82, 168, 157, 168, 157, 155, 107, 75, 137, 75, 129, 121, 129, 121, 93, 143, 93, 143, 28, 170, 28, 125, 167, 125, 130, 161, 130, 161, 122, 147, 122, 147, 117, 159, 117, 123, 85, 123, 85, 120, 81, 120, 81, 49, 111, 49, 111, 134, 111, 35, 111, 35, 114, 139, 114, 35, 114, 35, 110, 97, 110, 97, 72, 102, 72, 151, 140, 151, 21, 59, 21, 59, 100, 109, 100, 109, 38, 42, 38, 42, 43, 64, 43, 64, 108, 141, 108, 141, 80, 33, 80, 33, 70, 90, 70, 90, 77, 124, 77, 66, 128, 66, 128, 29, 39, 29, 39, 169, 112, 169, 39, 169, 39, 98, 68, 98, 68, 89, 150, 89, 4, 162, 4, 162, 44, 58, 44, 58, 148, 153, 148, 153, 25, 153, 25, 63, 74, 63, 74, 69, 106, 69, 106, 51, 24, 51, 24, 76, 62, 76, 62, 105, 83, 105, 83, 20, 48, 20, 48, 27, 133, 27, 133, 10, 3, 10, 3, 126, 84, 126, 84, 88, 52, 88, 52, 46, 55, 46, 55, 18, 12, 18, 12, 0, 115, 0, 115, 67, 73, 67, 73, 32, 2, 32, 2, 19, 113, 19, 113, 9, 23, 9, 23, 41, 53, 41, 53, 11, 65, 11, 65, 6, 13, 6, 13, 56, 5, 56, 5, 37, 14, 37, 14, 94, 95, 94, 95, 30, 36, 30, 36, 45, 26, 45, 26, 16, 8, 16, 8, 71, 31, 71, 31, 7, 87, 7, 87, 17, 34, 17, 34, 22, 60, 22, 60, 78, 1, 78, 1, 15 }

45
32
{36, 1, 27, 8, 35, 11, 20, 32, 15, 37, 39, 7, 34, 24, 6, 16, 41, 29, 26, 33, 40, 2, 10, 43, 18, 0, 28, 14, 13, 3, 44, 12, 17, 31, 30, 42, 5, 4, 38, 25, 22, 21, 9, 19, 0, 1, 25, 1, 12, 6, 5, 25, 43, 41, 42, 34, 7, 44, 13, 38, 42, 36, 20, 29, 43, 6, 10, 15, 38, 7, 41, 0, 4, 27, 4, 37, 38, 28, 10, 28, 4, 25, 38, 32, 16, 19, 7, 35, 9, 36, 43, 37, 34, 12, 11, 36, 12, 9, 37, 26, 23, 3, 5, 20, 25, 4, 15, 26, 5, 7, 14, 9, 34, 40, 35, 32, 35, 13, 36, 38, 21, 9, 41, 18, 13, 35, 2, 10, 13, 36, 27, 4, 6, 31, 4, 9, 4, 41, 21, 36, 44, 15, 11, 18, 19, 9, 15, 34, 44, 42, 14, 41, 37, 27, 34, 39, 41, 1, 10, 15, 29, 27, 13, 12, 36, 30, 39, 42, 31, 31, 0, 35, 42, 19, 1, 43, 28, 44, 18, 33, 26, 44, 13, 22, 34, 29, 44, 41, 29, 36, 16, 13, 35, 44, 1, 7, 15, 10, 13, 17, 19, 22, 15, 26, 17, 32, 19, 12, 23, 41, 14, 29, 21, 18, 39, 3, 28, 7, 31, 23, 26, 42, 43, 9, 12, 30, 13, 33, 28, 27, 2, 40, 19, 22, 37, 40, 29, 16, 33, 5, 31, 42, 34, 33, 28, 39, 39, 5, 16, 0, 21, 11, 9, 24, 29, 19, 1, 14, 34, 25, 10, 24, 26, 16, 34, 2, 35, 35, 32, 1, 44, 0, 1, 18, 4, 37, 37, 34, 35, 5, 18, 9, 25, 44, 39, 14, 12, 28, 2, 19}
{23, 23, 1, 23, 1, 36, 35, 27, 32, 20, 15, 32, 35, 32, 24, 15, 6, 34, 7, 23, 23, 8, 8, 36, 26, 11, 39, 24, 0, 11, 40, 35, 27, 7, 34, 40, 13, 41, 24, 29, 7, 8, 30, 1, 40, 10, 21, 33, 4, 40, 25, 1, 17, 37, 36, 2, 20, 28, 22, 23, 41, 21, 40, 10, 11, 39, 35, 19, 43, 11, 27, 38, 30, 23, 16, 13, 17, 12, 30, 19, 21, 10, 40, 1, 31, 24, 34, 8, 17, 12, 20, 11, 12, 6, 6, 25, 31, 8, 23, 23, 5, 31, 6, 0, 20, 31, 21, 10, 37, 33, 38, 33, 32, 12, 23, 21, 13, 11, 2, 39, 26, 16, 20, 12, 33, 16, 20, 39, 14, 10, 37, 35, 16, 42, 18, 11, 44, 3, 38, 14, 35, 23, 33, 23, 25, 4, 11, 13, 30, 37, 25, 10, 17, 7, 3, 29, 21, 2, 11, 10, 24, 21, 39, 22, 34, 16, 27, 30, 30, 25, 22, 29, 32, 33, 34, 24, 21, 38, 33, 25, 3, 16, 2, 43, 20, 7, 18, 38, 14, 8, 40, 16, 7, 17, 39, 3, 42, 5, 25, 5, 17, 32, 36, 33, 3, 2, 41, 38, 32, 26, 1, 9, 33, 14, 23, 8, 13, 17, 2, 14, 19, 33, 26, 28, 27, 28, 20, 12, 17, 22, 5, 39, 36, 42, 43, 13, 20, 7, 43, 32, 29, 11, 10, 38, 4, 0, 26, 40, 41, 10, 19, 2, 23, 34, 27, 10, 42, 7, 8, 42, 3, 7, 37, 19, 17, 44, 5, 39, 44, 16, 10, 36, 8, 29, 19, 36, 10, 5, 11, 7, 43, 2, 4, 36, 43, 35, 2, 23, 40, 18}
Returns: {32, 1, 2, 5, 6, 11, 0, 10, 0, 11, 6, 5, 2, 1, 10, 3, 7, 14, 13, 16, 4, 9, 8, 21, 15, 19, 17, 27, 12, 18, 23, 26, 33, 25, 20, 29, 24, 34, 30, 28, 39, 35, 44, 36, 37, 41, 38, 40, 42, 22, 43, 22, 42, 22, 42, 31, 42, 40, 42, 40, 38, 41, 38, 41, 37, 36, 37, 36, 44, 35, 44, 35, 39, 28, 39, 28, 30, 34, 30, 34, 24, 29, 24, 29, 20, 25, 20, 25, 33, 26, 33, 26, 23, 18, 23, 18, 12, 27, 12, 27, 17, 19, 17, 19, 15, 21, 15, 21, 8, 9, 8, 9, 4, 16, 4, 16, 13, 14, 13, 14, 7, 3, 7, 3, 10, 0, 11, 6, 5, 2, 1, 32 }

Submissions are judged against all 91 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PaintItBlack with a public method vector<int> findWalk(int n, int u, vector<int> a, vector<int> b) · 91 test cases · 2 s / 256 MB per case