# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
367526 | 2021-02-17T15:25:44 Z | spatarel | Travelling Salesperson (CCO20_day2problem1) | C++17 | 1 ms | 384 KB |
#include <stdio.h> #include <stack> int main() { int n; scanf("%d", &n); bool color[1 + n][1 + n]; for (int i = 1; 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 0 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 0 ms | 364 KB | Output is correct |
7 | Correct | 0 ms | 364 KB | Output is correct |
8 | Incorrect | 0 ms | 364 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |