QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#416065#4513. Slide ParadeWhicy0 0ms0kbC++202.1kb2024-05-21 15:40:372024-05-21 15:40:37

Judging History

你现在查看的是最新测评结果

  • [2024-05-21 15:40:37]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-05-21 15:40:37]
  • 提交

answer

#include <ios>
#include <iostream>
#include <vector>
int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int T;
  std::cin >> T;
  for (int TC = 1; TC <= T; TC++) {
    std::cout << "Case #" << TC << ": ";
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> ed(n);
    for (int i = 0; i < m; i++) {
      int u, v;
      std::cin >> u >> v;
      ed[--u].push_back(--v);
    }
    std::vector<int> lnk(n, -1), vis(n, 0);
    auto dfs = [&](const auto &dfs, const int &u, std::vector<bool> &vis) -> bool {
      for (int v : ed[u]) {
        if (vis[v])
          continue;
        vis[v] = 1;
        if (!~lnk[v] || dfs(dfs, lnk[v], vis)) {
          lnk[v] = u;
          return true;
        }
      }
      return false;
    };
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      std::vector<bool> vis(n, 0);
      if (dfs(dfs, i, vis))
        cnt++;
    }
    if (cnt < n) {
      std::cout << "IMPOSSIBLE\n";
      continue;
    }
    std::vector<std::vector<int>> nwed(n);
    for (int u = 0; u < n; u++) {
      for (auto v : ed[u]) {
        if (lnk[v] == u) {
          for (int i = 0; i < n; i++) {
            nwed[lnk[i]].push_back(i);
          }
          continue;
        }
        for (int i = 0; i < n; i++)
          if (lnk[i] == u)
            lnk[i] = -1;
        int tmp = lnk[v];
        lnk[v] = u;
        std::vector<bool> vis(n, 0);
        vis[v] = 1;
        dfs(dfs, tmp, vis);
        for (int i = 0; i < n; i++) {
          nwed[lnk[i]].push_back(i);
        }
      }
    }
    std::cout << n * m + 1 << "\n";
    std::vector<int> ans;
    auto fnd = [&](auto fnd, int u) -> void {
      for (auto &x : nwed[u]) {
        int v = x;
        if (!~v)
          continue;
        x = -1;
        fnd(fnd, v);
        ans.push_back(u);
      }
    };
    fnd(fnd, 1);
    int st = 0;
    for (; ans[st] != 0; st++)
      ;
    for (int i = st; i < n * m; i++) {
      std::cout << ans[i] + 1 << " ";
    }
    for (int i = 0; i < st; i++) {
      std::cout << ans[i] + 1 << " ";
    }
    std::cout << "1\n";
  }
}

详细

Test #1:

score: 0
Runtime Error

input:

100
5 8
1 2
1 3
1 4
1 5
2 1
3 1
4 1
5 1
5 10
1 3
1 4
2 3
2 5
3 1
3 4
3 5
4 2
5 1
5 3
5 10
1 4
2 3
2 5
3 1
3 5
4 2
4 3
4 5
5 1
5 2
3 6
1 2
1 3
2 1
2 3
3 1
3 2
5 10
1 2
1 5
2 3
2 4
3 1
4 3
4 5
5 2
5 3
5 4
4 10
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 4
4 2
4 3
5 10
1 2
1 3
2 1
2 4
3 1
3 5
4 2
4 5
5 3
5 4
5 10
1 ...

output:


result:


Test #2:

score: 0
Runtime Error

input:

100
199 4980
1 95
1 96
1 105
1 124
1 130
1 131
1 135
1 137
1 139
1 140
1 141
1 147
1 155
1 172
1 174
1 179
1 183
1 188
1 193
1 196
1 197
2 3
2 5
2 13
2 14
2 17
2 20
2 24
2 26
2 30
2 41
2 44
2 45
2 52
2 56
2 67
2 70
2 71
2 74
2 78
2 84
2 85
2 90
2 92
2 93
2 97
2 107
2 111
2 113
2 122
2 124
2 128
2 13...

output:


result: