Submission #367532

#	Time	Username	Problem	Language	Result	Execution time	Memory
367532		spatarel	Travelling Salesperson (CCO20_day2problem1)	C++17	25 / 25	483 ms	24316 KiB

Main

#include <stdio.h>
#include <stack>

int main() {
  int n;
  scanf("%d", &n);
  bool color[1 + n][1 + n];
  char edges[1 + n + 1];
  for (int i = 2; i <= n; i++) {
    scanf("%s", edges + 1);
    for (int j = 1; j < i; j++) {
      color[i][j] = color[j][i] = (edges[j] == '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 (stderr)

Main.cpp: In function 'int main()':
Main.cpp:6:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    6 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
Main.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |     scanf("%s", edges + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25