# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
367529 | 2021-02-17T15:34:53 Z | spatarel | Travelling Salesperson (CCO20_day2problem1) | C++17 | 639 ms | 24556 KB |
#include <stdio.h> #include <stack> int main() { int n; scanf("%d", &n); bool color[1 + n][1 + n]; for (int i = 2; i <= n; i++) { scanf("\n"); for (int j = 1; j < i; j++) { char edge; scanf("%c", &edge); color[i][j] = color[j][i] = (edge == 'R'); } } int vertices[1 + n]; for (int u = 1; u <= n; u++) { vertices[u] = u; } for (int end = 1; end <= n; end++) { std::stack<int> reds; std::stack<int> greens; std::swap(vertices[end], vertices[n]); for (int i = 1; i <= n; i++) { int u = vertices[i]; if (reds.empty() || color[reds.top()][u]) { reds.push(u); } else if (greens.empty() || !color[greens.top()][u]) { greens.push(u); } else if (color[reds.top()][greens.top()]) { reds.push(greens.top()); greens.pop(); reds.push(u); } else { greens.push(reds.top()); reds.pop(); greens.push(u); } } std::swap(vertices[end], vertices[n]); if (!greens.empty() && greens.top() == end) { std::swap(reds, greens); } printf("%d\n", n); while (!reds.empty()) { printf("%d ", reds.top()); reds.pop(); } while (!greens.empty()) { printf("%d ", greens.top()); greens.pop(); } printf("\n"); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 0 ms | 256 KB | Output is correct |
5 | Correct | 0 ms | 256 KB | Output is correct |
6 | Correct | 1 ms | 256 KB | Output is correct |
7 | Correct | 0 ms | 256 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 0 ms | 364 KB | Output is correct |
13 | Correct | 0 ms | 364 KB | Output is correct |
14 | Correct | 0 ms | 364 KB | Output is correct |
15 | Correct | 0 ms | 364 KB | Output is correct |
16 | Correct | 556 ms | 24172 KB | Output is correct |
17 | Correct | 547 ms | 24044 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 576 ms | 23884 KB | Output is correct |
20 | Correct | 558 ms | 24300 KB | Output is correct |
21 | Correct | 1 ms | 364 KB | Output is correct |
22 | Correct | 530 ms | 24172 KB | Output is correct |
23 | Correct | 558 ms | 24044 KB | Output is correct |
24 | Correct | 2 ms | 364 KB | Output is correct |
25 | Correct | 544 ms | 23796 KB | Output is correct |
26 | Correct | 570 ms | 24044 KB | Output is correct |
27 | Correct | 34 ms | 1644 KB | Output is correct |
28 | Correct | 559 ms | 24300 KB | Output is correct |
29 | Correct | 536 ms | 23956 KB | Output is correct |
30 | Correct | 532 ms | 24044 KB | Output is correct |
31 | Correct | 539 ms | 23916 KB | Output is correct |
32 | Correct | 573 ms | 23872 KB | Output is correct |
33 | Correct | 530 ms | 24100 KB | Output is correct |
34 | Correct | 556 ms | 23916 KB | Output is correct |
35 | Correct | 553 ms | 24044 KB | Output is correct |
36 | Correct | 611 ms | 24172 KB | Output is correct |
37 | Correct | 530 ms | 24044 KB | Output is correct |
38 | Correct | 575 ms | 24044 KB | Output is correct |
39 | Correct | 593 ms | 23952 KB | Output is correct |
40 | Correct | 525 ms | 24148 KB | Output is correct |
41 | Correct | 543 ms | 23916 KB | Output is correct |
42 | Correct | 525 ms | 23916 KB | Output is correct |
43 | Correct | 546 ms | 24100 KB | Output is correct |
44 | Correct | 549 ms | 23836 KB | Output is correct |
45 | Correct | 547 ms | 24208 KB | Output is correct |
46 | Correct | 562 ms | 23960 KB | Output is correct |
47 | Correct | 607 ms | 24044 KB | Output is correct |
48 | Correct | 583 ms | 23876 KB | Output is correct |
49 | Correct | 549 ms | 24116 KB | Output is correct |
50 | Correct | 527 ms | 23916 KB | Output is correct |
51 | Correct | 628 ms | 23800 KB | Output is correct |
52 | Correct | 556 ms | 24044 KB | Output is correct |
53 | Correct | 543 ms | 24044 KB | Output is correct |
54 | Correct | 561 ms | 24392 KB | Output is correct |
55 | Correct | 560 ms | 24556 KB | Output is correct |
56 | Correct | 551 ms | 24172 KB | Output is correct |
57 | Correct | 563 ms | 24172 KB | Output is correct |
58 | Correct | 552 ms | 24248 KB | Output is correct |
59 | Correct | 550 ms | 24044 KB | Output is correct |
60 | Correct | 550 ms | 24188 KB | Output is correct |
61 | Correct | 542 ms | 24264 KB | Output is correct |
62 | Correct | 549 ms | 24096 KB | Output is correct |
63 | Correct | 566 ms | 24172 KB | Output is correct |
64 | Correct | 556 ms | 24044 KB | Output is correct |
65 | Correct | 632 ms | 24052 KB | Output is correct |
66 | Correct | 578 ms | 24300 KB | Output is correct |
67 | Correct | 557 ms | 24172 KB | Output is correct |
68 | Correct | 537 ms | 24172 KB | Output is correct |
69 | Correct | 555 ms | 24172 KB | Output is correct |
70 | Correct | 551 ms | 24044 KB | Output is correct |
71 | Correct | 535 ms | 24176 KB | Output is correct |
72 | Correct | 561 ms | 24172 KB | Output is correct |
73 | Correct | 571 ms | 24044 KB | Output is correct |
74 | Correct | 542 ms | 24044 KB | Output is correct |
75 | Correct | 627 ms | 24092 KB | Output is correct |
76 | Correct | 539 ms | 24172 KB | Output is correct |
77 | Correct | 598 ms | 24044 KB | Output is correct |
78 | Correct | 548 ms | 24172 KB | Output is correct |
79 | Correct | 544 ms | 24428 KB | Output is correct |
80 | Correct | 545 ms | 24068 KB | Output is correct |
81 | Correct | 542 ms | 24076 KB | Output is correct |
82 | Correct | 547 ms | 24044 KB | Output is correct |
83 | Correct | 539 ms | 24044 KB | Output is correct |
84 | Correct | 622 ms | 24044 KB | Output is correct |
85 | Correct | 639 ms | 24180 KB | Output is correct |
86 | Correct | 548 ms | 24044 KB | Output is correct |
87 | Correct | 34 ms | 1644 KB | Output is correct |
88 | Correct | 35 ms | 1644 KB | Output is correct |
89 | Correct | 565 ms | 24056 KB | Output is correct |
90 | Correct | 542 ms | 24044 KB | Output is correct |
91 | Correct | 43 ms | 1792 KB | Output is correct |
92 | Correct | 33 ms | 1644 KB | Output is correct |
93 | Correct | 553 ms | 24364 KB | Output is correct |
94 | Correct | 551 ms | 24172 KB | Output is correct |
95 | Correct | 34 ms | 1644 KB | Output is correct |
96 | Correct | 36 ms | 1644 KB | Output is correct |
97 | Correct | 549 ms | 24300 KB | Output is correct |
98 | Correct | 550 ms | 24172 KB | Output is correct |