DrivingPlans
SRM 624 · 2013-12-22 · by ivan_metelsky
SRM 624 · 2013-12-22 · by ivan_metelsky · Advanced Math, Graph Theory, Math
Problem Statement
Problem Statement
You live in a city with N intersections, numbered 1 through N. There are some roads in the city. Each road is bidirectional and connects two intersections. There are no loops and each pair of intersections is connected by at most one road. The road network is connected - that is, one can travel between any two intersections.
A special feature of this city is that some of the roads have no speed limits, and everyone drives along those roads at an insane speed. For the purpose of this problem, we will simply assume that these roads can be traversed instantly, in zero time.
You are given the
You are currently at the intersection 1 and you want to travel to the intersection N as quickly as possible. Count all ways of doing so, and return that count modulo 1,000,000,009. If there are infinitely many ways, return -1 instead. (Two ways are considered different if the sequences of visited intersections differ. Note that it is allowed to enter any intersection, including intersections 1 and N, multiple times.)
Constraints
- N will be between 2 and 2,000, inclusive.
- A, B and C will contain between 1 and 2,000 elements, inclusive.
- A, B and C will contain the same number of elements.
- Each element of A and B will be between 1 and N, inclusive.
- Each element of C will be between 0 and 100,000, inclusive.
- For each valid i, A[i] will be different from B[i].
- No two roads will connect the same pair of intersections.
- The road network will be connected.
Examples
0)
4
{1,1,2,3}
{2,3,4,4}
{1,1,1,1}
Returns: 2
There are exactly two shortest ways of travel: 1-2-4 and 1-3-4.
1)
4
{1,1,2,3}
{2,3,4,4}
{1,1,1,0}
Returns: -1
Remember that each road can be used in both directions. In this case, there are infinitely many ways how to reach the intersection 4 in shortest time. For example, you can go 1-3-4, or 1-3-4-3-4, or 1-3-4-3-4-3-4, etc.
2)
7
{1,1,2,3,4,4,5,6}
{2,3,4,4,5,6,7,7}
{1,1,2,2,3,3,4,4}
Returns: 4
3)
1000
{602, 602, 474, 982, 982, 89, 524, 524, 761, 445, 546, 108, 108, 176, 176, 970, 970, 993, 498, 366, 695, 880, 880, 321, 321, 247, 928, 928, 741, 819, 109, 582, 973, 973, 558, 558, 149, 149, 614, 397, 46, 985, 355, 355, 587, 57, 57, 364, 364, 895, 432, 399, 965, 387, 387, 682, 592, 788, 788, 141, 141, 495, 840, 147, 107, 107, 518, 584, 584, 78, 96, 96, 256, 776, 797, 390, 390, 417, 567, 567, 658, 76, 649, 520, 207, 207, 553, 553, 749, 90, 646, 564, 564, 636, 505, 9, 380, 380, 544, 534, 979, 979, 270, 516, 358, 97, 97, 575, 575, 830, 689, 440, 440, 709, 709, 942, 942, 174, 771, 197, 274, 274, 654, 483, 449, 449, 613, 199, 199, 198, 783, 526, 50, 50, 923, 803, 51, 51, 333, 333, 164, 642, 45, 580, 200, 858, 742, 742, 226, 129, 312, 224, 192, 192, 511, 669, 315, 127, 127, 168, 926, 438, 456, 196, 927, 927, 902, 902, 678, 852, 672, 317, 317, 806, 150, 989, 989, 826, 515, 811, 740, 967, 517, 834, 561, 561, 281, 293, 293, 772, 117, 560, 739, 739, 159, 159, 3, 707, 692, 957, 887, 637, 260, 69, 69, 766, 766, 138, 138, 701, 701, 16, 295, 674, 674, 104, 271, 301, 301, 936, 936, 565, 565, 835, 203, 686, 661, 316, 316, 878, 717, 717, 817, 937, 838, 536, 536, 485, 485, 655, 655, 812, 625, 625, 151, 381, 578, 818, 818, 572, 529, 83, 867, 545, 545, 673, 767, 963, 522, 522, 7, 792, 656, 656, 694, 694, 542, 758, 758, 29, 65, 922, 37, 941, 532, 532, 574, 103, 675, 675, 336, 336, 947, 444, 322, 322, 836, 620, 61, 346, 639, 870, 827, 827, 657, 489, 489, 999, 999, 377, 114, 165, 265, 265, 44, 280, 280, 914, 32, 952, 144, 406, 406, 801, 610, 992, 172, 172, 447, 67, 849, 600, 931, 299, 388, 87, 457, 599, 725, 220, 220, 631, 131, 702, 721, 470, 539, 466, 466, 182, 297, 297, 562, 843, 20, 908, 994, 846, 716, 716, 111, 744, 744, 864, 864, 361, 361, 324, 986, 896, 873, 873, 577, 623, 493, 493, 618, 538, 753, 798, 798, 378, 991, 991, 428, 221, 514, 514, 837, 277, 298, 298, 331, 521, 795, 795, 305, 737, 737, 659, 263, 263, 688, 728, 892, 892, 912, 881, 881, 225, 954, 954, 984, 984, 294, 756, 997, 73, 262, 345, 345, 601, 77, 781, 723, 712, 712, 844, 458, 238, 876, 645, 645, 785, 136, 136, 918, 33, 33, 319, 757, 779, 275, 463, 804, 804, 134, 543, 784, 784, 433, 389, 621, 949, 949, 240, 924, 924, 588, 588, 789, 789, 189, 300, 300, 58, 777, 777, 550, 832, 832, 430, 452, 452, 951, 171, 860, 362, 179, 697, 697, 370, 370, 177, 648, 530, 530, 502, 34, 34, 448, 231, 231, 286, 961, 48, 955, 230, 8, 8, 383, 106, 106, 450, 504, 504, 284, 765, 685, 173, 173, 180, 471, 471, 212, 958, 778, 527, 627, 815, 815, 276, 146, 146, 557, 548, 143, 752, 752, 724, 851, 851, 215, 215, 590, 590, 75, 320, 24, 396, 396, 676, 98, 98, 392, 497, 497, 736, 414, 414, 635, 252, 310, 310, 990, 990, 768, 218, 218, 563, 563, 120, 233, 677, 376, 916, 156, 156, 402, 402, 119, 839, 925, 250, 250, 966, 148, 469, 469, 747, 747, 81, 971, 971, 882, 882, 36, 684, 684, 74, 704, 704, 488, 488, 79, 2, 962, 570, 479, 842, 228, 228, 473, 897, 769, 571, 571, 94, 94, 306, 977, 490, 490, 845, 845, 303, 760, 760, 344, 344, 850, 296, 581, 372, 372, 644, 644, 981, 981, 242, 257, 257, 261, 481, 313, 19, 178, 178, 56, 126, 831, 885, 193, 162, 227, 227, 133, 379, 664, 664, 258, 718, 718, 451, 451, 946, 343, 343, 476, 62, 62, 64, 884, 884, 854, 917, 232, 341, 341, 508, 868, 691, 691, 6, 828, 998, 998, 88, 519, 484, 484, 871, 871, 223, 667, 501, 501, 743, 743, 279, 412, 412, 934, 934, 365, 272, 272, 349, 349, 763, 773, 773, 405, 668, 422, 332, 332, 482, 359, 359, 662, 329, 606, 713, 726, 608, 39, 403, 102, 102, 42, 552, 872, 872, 384, 938, 863, 863, 52, 841, 800, 431, 431, 960, 35, 47, 47, 155, 125, 239, 239, 304, 730, 442, 435, 609, 609, 487, 145, 188, 237, 512, 135, 391, 132, 289, 289, 477, 531, 531, 612, 583, 583, 404, 128, 911, 593, 593, 121, 732, 395, 395, 54, 54, 974, 974, 472, 472, 494, 460, 460, 968, 802, 865, 715, 715, 434, 434, 746, 903, 793, 862, 323, 427, 427, 216, 894, 972, 206, 206, 980, 167, 167, 335, 400, 400, 889, 889, 415, 770, 633, 633, 68, 201, 201, 617, 666, 523, 905, 905, 630, 99, 462, 462, 12, 248, 660, 660, 195, 175, 808, 808, 738, 287, 139, 273, 273, 915, 547, 547, 214, 597, 116, 929, 759, 759, 41, 814, 559, 49, 413, 598, 373, 969, 568, 1, 964, 710, 710, 60, 352, 59, 59, 579, 14, 624, 624, 351, 719, 719, 681, 780, 10, 983, 913, 913, 30, 285, 468, 468, 416, 566, 566, 491, 43, 683, 683, 85, 278, 278, 586, 750, 750, 186, 920, 314, 314, 202, 202, 154, 110, 140, 140, 368, 92, 92, 883, 883, 734, 11, 541, 541, 696, 142, 17, 401, 254, 112, 510, 100, 100, 727, 650, 302, 302, 93, 160, 663, 663, 809, 729, 764, 711, 711, 21, 18, 18, 919, 919, 879, 290, 72, 533, 653, 576, 680, 680, 988, 184, 184, 347, 385, 356, 679, 500, 500, 693, 382, 429, 348, 348, 86, 475, 475, 229, 411, 219, 589, 589, 822, 959, 31, 53, 283, 235, 235, 25, 25, 794, 169, 945, 869, 455, 995, 443, 443, 334, 241, 241, 893, 893, 492, 492, 40, 605, 605, 731, 266, 266, 906, 906, 486, 486, 181, 181, 615, 848, 363, 363}
{243, 670, 670, 474, 89, 629, 629, 761, 445, 891, 891, 546, 540, 540, 706, 706, 993, 288, 288, 498, 366, 695, 1000, 1000, 247, 810, 810, 790, 790, 741, 819, 109, 582, 245, 245, 113, 113, 614, 397, 46, 22, 22, 985, 587, 705, 705, 130, 130, 762, 762, 895, 432, 399, 965, 152, 152, 682, 592, 374, 374, 495, 840, 360, 360, 147, 71, 71, 518, 78, 813, 813, 755, 755, 256, 776, 797, 246, 246, 417, 658, 76, 439, 439, 649, 520, 824, 824, 749, 90, 754, 754, 646, 636, 859, 859, 505, 9, 596, 596, 544, 534, 270, 191, 191, 516, 358, 267, 267, 478, 478, 830, 689, 619, 619, 652, 652, 480, 480, 174, 771, 197, 441, 441, 654, 483, 613, 194, 194, 198, 611, 611, 783, 526, 923, 803, 187, 187, 425, 425, 164, 408, 408, 642, 45, 580, 200, 858, 226, 528, 528, 129, 312, 224, 511, 669, 315, 786, 786, 168, 926, 438, 456, 196, 910, 910, 236, 236, 921, 921, 678, 852, 672, 806, 325, 325, 150, 826, 515, 811, 740, 496, 496, 967, 517, 834, 342, 342, 281, 772, 117, 560, 419, 419, 13, 13, 3, 707, 692, 350, 350, 957, 887, 637, 260, 549, 549, 268, 268, 158, 158, 16, 464, 464, 295, 104, 535, 535, 271, 157, 157, 782, 782, 393, 393, 835, 203, 686, 661, 616, 616, 878, 817, 353, 353, 937, 838, 253, 253, 328, 328, 70, 70, 812, 151, 211, 211, 381, 578, 572, 529, 461, 461, 83, 867, 622, 622, 673, 767, 963, 7, 823, 823, 792, 410, 410, 91, 91, 542, 29, 65, 922, 28, 28, 37, 941, 574, 38, 38, 103, 820, 820, 947, 444, 733, 733, 836, 620, 61, 170, 170, 346, 639, 870, 657, 847, 847, 904, 904, 377, 634, 634, 114, 165, 44, 594, 594, 914, 32, 952, 708, 708, 144, 327, 327, 801, 610, 992, 447, 67, 849, 311, 311, 600, 931, 299, 388, 87, 457, 599, 725, 631, 131, 209, 209, 702, 721, 470, 539, 182, 603, 603, 562, 843, 20, 205, 205, 908, 994, 846, 111, 900, 900, 84, 84, 80, 80, 324, 986, 896, 722, 722, 556, 556, 577, 623, 506, 506, 618, 538, 753, 378, 185, 185, 428, 221, 115, 115, 837, 337, 337, 277, 331, 521, 507, 507, 305, 166, 166, 907, 907, 659, 123, 123, 688, 728, 735, 735, 912, 225, 898, 898, 901, 901, 294, 756, 997, 73, 816, 816, 262, 601, 77, 781, 723, 124, 124, 844, 458, 238, 876, 394, 394, 785, 340, 340, 987, 987, 918, 319, 757, 857, 857, 779, 275, 463, 134, 339, 339, 543, 433, 210, 210, 389, 621, 643, 643, 240, 720, 720, 163, 163, 189, 647, 647, 58, 421, 421, 550, 513, 513, 604, 604, 430, 951, 171, 525, 525, 860, 362, 179, 255, 255, 177, 648, 537, 537, 978, 978, 502, 853, 853, 448, 286, 961, 48, 955, 856, 856, 230, 357, 357, 383, 450, 554, 554, 284, 765, 555, 555, 685, 269, 269, 180, 930, 930, 212, 958, 778, 527, 627, 276, 874, 874, 557, 548, 890, 890, 143, 724, 855, 855, 585, 585, 899, 899, 909, 909, 75, 320, 24, 676, 308, 308, 407, 407, 392, 956, 956, 736, 635, 252, 122, 122, 291, 291, 204, 204, 768, 875, 875, 120, 233, 940, 940, 677, 376, 916, 101, 101, 153, 153, 119, 839, 925, 966, 148, 665, 665, 932, 932, 81, 330, 330, 886, 886, 640, 640, 36, 418, 418, 74, 251, 251, 79, 2, 962, 638, 638, 570, 479, 842, 473, 282, 282, 897, 769, 264, 264, 975, 975, 306, 977, 569, 569, 423, 423, 303, 338, 338, 27, 27, 850, 296, 581, 703, 703, 976, 976, 105, 105, 242, 261, 481, 313, 19, 436, 436, 56, 126, 831, 453, 453, 885, 193, 162, 133, 379, 796, 796, 258, 307, 307, 935, 935, 55, 55, 946, 509, 509, 476, 64, 641, 641, 687, 687, 854, 917, 232, 508, 868, 208, 208, 6, 877, 877, 828, 95, 95, 88, 519, 23, 23, 223, 667, 222, 222, 690, 690, 279, 465, 465, 244, 244, 420, 420, 365, 888, 888, 763, 354, 354, 405, 668, 933, 933, 422, 482, 805, 805, 662, 699, 699, 329, 606, 713, 726, 608, 39, 403, 42, 552, 591, 591, 459, 459, 384, 938, 52, 841, 800, 950, 950, 960, 35, 607, 607, 155, 125, 213, 213, 304, 730, 442, 435, 807, 807, 487, 145, 118, 118, 188, 237, 512, 135, 391, 132, 371, 371, 477, 671, 671, 612, 551, 551, 404, 128, 911, 953, 953, 121, 732, 369, 369, 628, 628, 861, 861, 944, 944, 494, 183, 183, 968, 802, 865, 745, 745, 746, 903, 833, 833, 793, 862, 323, 216, 894, 190, 190, 972, 980, 161, 161, 335, 409, 409, 63, 63, 415, 770, 82, 82, 68, 386, 386, 617, 595, 595, 666, 523, 630, 99, 66, 66, 12, 787, 787, 248, 195, 175, 943, 943, 738, 367, 367, 287, 139, 249, 249, 915, 214, 748, 748, 597, 116, 929, 41, 814, 559, 49, 413, 598, 373, 292, 292, 969, 568, 1, 964, 60, 352, 398, 398, 579, 14, 866, 866, 351, 318, 318, 681, 780, 137, 137, 10, 983, 30, 454, 454, 285, 416, 437, 437, 375, 375, 491, 43, 446, 446, 85, 996, 996, 586, 573, 573, 186, 920, 774, 774, 154, 110, 799, 799, 368, 829, 829, 626, 626, 734, 26, 26, 11, 696, 142, 17, 401, 948, 948, 254, 112, 510, 727, 650, 4, 4, 651, 651, 93, 160, 809, 729, 309, 309, 764, 21, 503, 503, 234, 234, 879, 290, 5, 5, 72, 533, 653, 576, 988, 751, 751, 347, 385, 356, 259, 259, 679, 775, 775, 693, 382, 429, 467, 467, 86, 229, 411, 15, 15, 219, 822, 959, 632, 632, 31, 53, 283, 700, 700, 794, 169, 945, 326, 326, 869, 455, 995, 821, 821, 334, 424, 424, 217, 217, 40, 939, 939, 731, 791, 791, 825, 825, 499, 499, 698, 698, 426, 426, 615, 848, 714}
{0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1}
Returns: -1
4)
1000
{800, 567, 779, 290, 290, 933, 841, 841, 186, 767, 767, 852, 852, 192, 617, 617, 13, 776, 715, 238, 238, 375, 775, 775, 61, 627, 446, 265, 740, 612, 519, 519, 773, 473, 235, 946, 284, 522, 928, 553, 553, 310, 310, 524, 782, 538, 538, 492, 678, 141, 730, 730, 668, 668, 49, 50, 611, 611, 824, 824, 100, 100, 694, 694, 641, 361, 666, 705, 123, 218, 379, 379, 369, 136, 132, 132, 263, 672, 672, 161, 542, 673, 673, 458, 458, 33, 255, 960, 960, 14, 14, 23, 626, 333, 333, 167, 276, 154, 456, 111, 111, 613, 613, 432, 731, 113, 563, 563, 653, 653, 826, 826, 675, 193, 944, 988, 429, 17, 726, 900, 900, 882, 882, 248, 285, 285, 774, 599, 670, 670, 700, 700, 367, 455, 455, 601, 86, 364, 364, 820, 793, 283, 283, 604, 604, 984, 224, 224, 457, 1, 874, 97, 952, 499, 895, 254, 254, 371, 487, 275, 102, 102, 205, 281, 704, 980, 980, 180, 180, 887, 62, 150, 498, 498, 840, 407, 720, 720, 580, 53, 58, 690, 690, 794, 401, 90, 659, 84, 84, 454, 823, 839, 917, 917, 722, 830, 830, 261, 466, 466, 241, 241, 277, 242, 969, 185, 185, 475, 858, 350, 107, 916, 916, 963, 159, 530, 530, 75, 317, 317, 270, 539, 926, 892, 892, 857, 766, 785, 83, 83, 714, 964, 964, 959, 959, 523, 925, 765, 799, 799, 324, 324, 19, 544, 541, 541, 835, 437, 437, 433, 713, 482, 16, 985, 985, 417, 885, 326, 326, 172, 919, 52, 629, 506, 506, 953, 118, 118, 135, 585, 585, 329, 356, 571, 535, 535, 558, 589, 589, 287, 287, 842, 316, 64, 3, 3, 831, 140, 140, 596, 117, 260, 520, 520, 389, 674, 674, 594, 494, 792, 706, 864, 574, 660, 533, 228, 228, 719, 644, 644, 965, 965, 855, 474, 474, 121, 696, 696, 127, 915, 346, 346, 461, 54, 54, 978, 319, 319, 331, 548, 87, 890, 94, 94, 293, 293, 637, 313, 313, 387, 387, 881, 11, 56, 225, 656, 656, 191, 982, 614, 444, 288, 106, 106, 311, 676, 654, 654, 267, 684, 29, 509, 509, 187, 301, 122, 537, 941, 931, 931, 807, 226, 226, 229, 701, 981, 476, 145, 145, 504, 294, 294, 104, 153, 153, 411, 411, 752, 92, 465, 717, 880, 744, 744, 789, 789, 282, 693, 693, 373, 736, 108, 318, 968, 148, 148, 510, 403, 1000, 1000, 777, 143, 976, 623, 554, 554, 957, 957, 105, 266, 961, 961, 116, 116, 190, 412, 511, 197, 197, 872, 315, 351, 871, 871, 692, 71, 781, 577, 679, 77, 77, 556, 815, 152, 849, 279, 865, 399, 425, 942, 942, 979, 164, 96, 96, 201, 761, 718, 681, 681, 804, 804, 330, 330, 949, 203, 448, 24, 24, 665, 562, 992, 485, 485, 212, 828, 828, 682, 682, 257, 595, 305, 850, 850, 160, 160, 413, 610, 341, 938, 938, 269, 380, 380, 877, 877, 603, 603, 234, 868, 576, 223, 415, 415, 298, 588, 751, 549, 648, 648, 763, 763, 783, 923, 934, 551, 723, 723, 669, 383, 633, 756, 360, 863, 863, 764, 905, 467, 467, 605, 728, 600, 98, 921, 508, 508, 128, 128, 697, 363, 38, 137, 906, 303, 2, 196, 729, 860, 769, 347, 175, 175, 428, 80, 80, 488, 39, 771, 354, 354, 240, 51, 970, 181, 745, 745, 222, 222, 570, 657, 550, 391, 392, 392, 889, 889, 907, 907, 753, 753, 355, 396, 291, 291, 999, 171, 406, 44, 44, 716, 716, 451, 451, 803, 377, 103, 878, 780, 435, 579, 579, 250, 250, 165, 165, 998, 572, 528, 582, 643, 496, 496, 447, 546, 546, 370, 134, 995, 507, 507, 115, 220, 388, 471, 471, 384, 384, 966, 966, 26, 339, 339, 8, 936, 618, 991, 894, 894, 416, 70, 822, 822, 560, 560, 88, 987, 987, 125, 309, 309, 918, 183, 521, 734, 518, 677, 271, 57, 36, 36, 463, 552, 249, 486, 459, 459, 258, 322, 42, 42, 685, 348, 348, 28, 256, 256, 41, 440, 737, 893, 699, 699, 540, 838, 7, 786, 833, 833, 790, 790, 879, 973, 973, 581, 816, 710, 710, 424, 424, 427, 439, 439, 503, 337, 337, 813, 365, 983, 606, 606, 924, 810, 810, 179, 460, 460, 114, 151, 151, 708, 651, 667, 667, 495, 495, 438, 438, 272, 312, 221, 99, 545, 545, 10, 82, 569, 561, 561, 910, 374, 749, 634, 634, 866, 575, 419, 340, 512, 214, 534, 45, 156, 299, 908, 124, 619, 619, 209, 209, 18, 147, 671, 59, 555, 202, 202, 344, 755, 353, 353, 993, 993, 292, 79, 79, 711, 602, 856, 245, 625, 119, 119, 768, 332, 586, 5, 5, 409, 975, 505, 239, 742, 742, 557, 825, 640, 640, 832, 759, 759, 937, 997, 997, 578, 195, 661, 37, 37, 886, 843, 362, 362, 55, 55, 405, 748, 328, 328, 170, 60, 566, 566, 939, 939, 955, 204, 204, 584, 532, 532, 639, 63, 63, 366, 206, 502, 502, 622, 236, 178, 178, 493, 621, 67, 67, 721, 176, 27, 583, 583, 199, 320, 320, 943, 631, 655, 707, 707, 645, 645, 609, 484, 189, 101, 184, 184, 598, 598, 515, 515, 695, 784, 784, 898, 336, 336, 818, 818, 109, 74, 513, 513, 724, 359, 829, 829, 76, 564, 564, 883, 791, 791, 536, 338, 758, 758, 246, 246, 268, 821, 821, 922, 922, 480, 741, 133, 927, 927, 812, 904, 904, 757, 986, 688, 688, 811, 78, 78, 805, 805, 253, 253, 787, 787, 845, 73, 73, 703, 321, 733, 434, 650, 650, 709, 166, 297, 95, 903, 903, 920, 920, 687, 211, 243, 40, 40, 130, 531, 93, 93, 126, 747, 445, 177, 177, 616, 568, 478, 479, 806, 302, 302, 345, 861, 636, 357, 630, 615, 615, 163, 163, 628, 213, 896, 259, 259, 46, 138, 138, 827, 772, 689, 426, 862, 862, 873, 404, 381, 770, 325, 278, 278, 296, 296, 958, 525, 501, 468, 559, 219, 61, 235, 141, 9, 432, 247, 283, 198, 102, 704, 58, 401, 277, 242, 746, 541, 326, 629, 118, 327, 289, 389, 706, 72, 982, 654, 509, 301, 752, 880, 736, 148, 197, 164, 201, 96, 448, 562, 576, 669, 728, 128, 363, 196, 391, 897, 907, 171, 780, 727, 449, 8, 416, 421, 918, 42, 28, 252, 790, 973, 424, 390, 337, 809, 114, 561, 156, 124, 202, 993, 79, 856, 661, 55, 566, 420, 584, 639, 971, 513, 829, 607, 757, 801, 6, 709, 211, 130, 896, 138, 138, 772}
{567, 779, 683, 683, 314, 314, 933, 186, 273, 273, 912, 912, 192, 951, 951, 13, 776, 219, 219, 715, 215, 215, 375, 61, 627, 446, 265, 740, 612, 490, 490, 773, 473, 514, 514, 235, 946, 284, 522, 928, 875, 875, 524, 782, 930, 930, 950, 950, 492, 678, 141, 217, 217, 49, 50, 491, 491, 642, 642, 646, 646, 972, 972, 453, 453, 641, 361, 666, 705, 123, 218, 795, 795, 369, 136, 778, 778, 263, 686, 686, 161, 542, 395, 395, 989, 989, 33, 255, 358, 358, 23, 626, 400, 400, 167, 276, 154, 456, 9, 9, 231, 231, 432, 731, 113, 174, 174, 909, 909, 194, 194, 675, 193, 944, 988, 429, 247, 247, 17, 726, 725, 725, 248, 597, 597, 774, 155, 155, 599, 962, 962, 367, 500, 500, 601, 954, 954, 86, 820, 386, 386, 793, 48, 48, 198, 198, 984, 457, 1, 874, 97, 952, 499, 895, 85, 85, 371, 378, 378, 487, 275, 205, 281, 704, 216, 216, 808, 808, 887, 884, 884, 62, 150, 840, 407, 69, 69, 580, 53, 58, 796, 796, 794, 837, 837, 401, 90, 659, 454, 823, 935, 935, 839, 664, 664, 722, 139, 139, 261, 452, 452, 277, 242, 969, 4, 4, 834, 834, 475, 858, 350, 107, 963, 649, 649, 159, 75, 47, 47, 270, 539, 662, 662, 926, 851, 851, 857, 766, 785, 477, 477, 714, 423, 423, 323, 323, 523, 925, 765, 743, 743, 739, 739, 19, 544, 746, 746, 835, 760, 760, 433, 713, 482, 16, 173, 173, 417, 885, 172, 919, 52, 629, 304, 304, 162, 162, 953, 135, 956, 956, 329, 334, 334, 356, 571, 327, 327, 558, 408, 408, 289, 289, 842, 316, 64, 831, 441, 441, 596, 117, 260, 306, 306, 732, 732, 389, 594, 494, 792, 43, 43, 706, 864, 574, 660, 533, 719, 207, 207, 442, 442, 855, 31, 31, 489, 489, 121, 81, 81, 127, 915, 72, 72, 461, 517, 517, 978, 331, 548, 87, 450, 450, 890, 632, 632, 443, 443, 637, 397, 397, 881, 11, 56, 144, 144, 225, 191, 982, 22, 22, 614, 444, 288, 311, 169, 169, 676, 267, 35, 35, 684, 29, 187, 702, 702, 301, 122, 537, 941, 847, 847, 807, 848, 848, 229, 701, 981, 476, 504, 168, 168, 131, 131, 104, 854, 854, 752, 295, 295, 92, 465, 717, 880, 230, 230, 990, 990, 282, 373, 736, 108, 318, 859, 859, 968, 510, 403, 142, 142, 777, 143, 888, 888, 976, 623, 307, 307, 105, 526, 526, 266, 470, 470, 817, 817, 190, 412, 511, 430, 430, 872, 315, 351, 89, 89, 692, 71, 781, 577, 679, 527, 527, 556, 815, 152, 849, 279, 865, 399, 425, 979, 25, 25, 164, 201, 761, 718, 899, 899, 497, 497, 876, 876, 949, 914, 914, 203, 448, 665, 853, 853, 562, 992, 464, 464, 212, 836, 836, 257, 595, 305, 385, 385, 232, 232, 413, 610, 341, 393, 393, 269, 691, 691, 870, 870, 698, 698, 234, 868, 576, 343, 343, 223, 298, 588, 237, 237, 751, 549, 587, 587, 783, 923, 934, 551, 120, 120, 669, 383, 274, 274, 633, 756, 360, 764, 905, 286, 286, 605, 728, 797, 797, 600, 98, 921, 349, 349, 697, 363, 38, 592, 592, 137, 906, 303, 2, 196, 729, 860, 769, 347, 428, 394, 394, 488, 39, 771, 573, 573, 240, 129, 129, 51, 970, 181, 264, 264, 738, 738, 570, 657, 550, 391, 68, 68, 897, 897, 788, 788, 469, 469, 355, 396, 335, 335, 999, 171, 406, 422, 422, 157, 157, 803, 377, 103, 878, 780, 435, 727, 727, 34, 34, 932, 932, 998, 572, 528, 382, 382, 582, 643, 447, 902, 902, 370, 134, 402, 402, 995, 115, 449, 449, 220, 388, 663, 663, 352, 352, 26, 996, 996, 8, 936, 618, 991, 244, 244, 802, 802, 416, 70, 911, 911, 867, 867, 88, 421, 421, 125, 918, 183, 521, 734, 547, 547, 518, 677, 271, 57, 463, 342, 342, 552, 249, 486, 258, 322, 462, 462, 685, 948, 948, 28, 252, 252, 913, 913, 41, 440, 737, 893, 540, 680, 680, 838, 7, 786, 590, 590, 879, 967, 967, 581, 762, 762, 816, 754, 754, 427, 390, 390, 974, 974, 503, 813, 635, 635, 365, 983, 924, 809, 809, 179, 712, 712, 114, 233, 233, 708, 651, 593, 593, 66, 66, 65, 65, 272, 112, 112, 312, 221, 99, 945, 945, 10, 82, 569, 182, 182, 910, 374, 749, 866, 575, 419, 340, 91, 91, 512, 214, 534, 45, 156, 299, 908, 124, 158, 158, 18, 147, 543, 543, 671, 59, 555, 638, 638, 344, 755, 750, 750, 292, 376, 376, 368, 368, 711, 602, 856, 245, 625, 768, 332, 947, 947, 586, 409, 975, 505, 239, 814, 814, 557, 825, 251, 251, 994, 994, 832, 227, 227, 937, 578, 195, 280, 280, 661, 886, 20, 20, 843, 149, 149, 405, 748, 262, 262, 110, 110, 170, 60, 420, 420, 955, 844, 844, 584, 735, 735, 200, 200, 639, 366, 971, 971, 206, 21, 21, 622, 236, 493, 647, 647, 621, 721, 176, 27, 565, 565, 414, 414, 199, 620, 620, 943, 631, 655, 300, 300, 609, 484, 189, 101, 30, 30, 652, 652, 410, 410, 695, 436, 436, 208, 208, 898, 846, 846, 109, 398, 398, 74, 431, 431, 724, 359, 76, 798, 798, 883, 591, 591, 607, 607, 536, 338, 624, 624, 869, 869, 268, 12, 12, 819, 819, 480, 741, 133, 812, 940, 940, 757, 188, 188, 986, 801, 801, 811, 308, 308, 901, 901, 418, 418, 845, 210, 210, 703, 6, 6, 321, 733, 434, 709, 529, 529, 166, 297, 95, 472, 472, 687, 211, 146, 146, 243, 130, 531, 929, 929, 126, 747, 445, 15, 15, 616, 568, 478, 608, 608, 479, 806, 345, 861, 636, 357, 630, 516, 516, 483, 483, 372, 372, 628, 213, 896, 46, 658, 658, 827, 32, 32, 772, 689, 426, 873, 404, 481, 481, 381, 770, 325, 977, 977, 891, 891, 958, 525, 501, 468, 13, 446, 473, 217, 231, 113, 988, 386, 48, 487, 980, 580, 794, 452, 241, 544, 835, 919, 919, 162, 589, 408, 520, 574, 915, 614, 169, 702, 187, 854, 465, 318, 403, 412, 979, 164, 761, 914, 485, 223, 120, 467, 363, 592, 860, 657, 68, 889, 335, 103, 780, 388, 996, 822, 88, 521, 948, 256, 913, 967, 879, 390, 974, 635, 179, 151, 82, 908, 158, 59, 353, 711, 711, 886, 748, 170, 60, 532, 532, 63, 398, 724, 338, 940, 78, 733, 434, 243, 929, 628, 46, 32, 827}
{0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0}
Returns: -1
Submissions are judged against all 315 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DrivingPlans with a public method int count(int N, vector<int> A, vector<int> B, vector<int> C) · 315 test cases · 2 s / 256 MB per case