QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#440245#8757. 图alpha1022WA 58ms3832kbC++141.6kb2024-06-13 14:16:382024-06-13 14:16:40

Judging History

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

  • [2024-06-13 14:16:40]
  • 评测
  • 测评结果:WA
  • 用时:58ms
  • 内存:3832kb
  • [2024-06-13 14:16:38]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

struct UnionFind {
  vector<int> fa;
  UnionFind(int n) : fa(n, -1) {}
  bool isRoot(int u) { return !~fa[u]; }
  int find(int u) { return isRoot(u) ? u : fa[u] = find(fa[u]); }
  bool isMerged(int u, int v) {
    int fu = find(u), fv = find(v);
    if (fu == fv) return 1;
    return 0;
  }
  void merge(int u, int v) {
    int fu = find(u), fv = find(v);
    if (fu == fv) return ;
    fa[fv] = fu;
  }
};

void solve() {
  int n, m, k; scanf("%d%d", &n, &m), k = (m + n - 1) / (n - 1);
  vector<vector<vector<int>>> e(k, vector<vector<int>>(n));
  vector<UnionFind> uf(k, n);
  int s = -1, t = -1;
  for (; m; --m) {
    int u, v; scanf("%d%d", &u, &v), --u, --v;
    int l = 0, r = k - 1, res = -1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (!uf[mid].isMerged(u, v)) r = mid - 1, res = mid;
      else l = mid + 1;
    }
    if (res == k - 1) s = u, t = v;
    uf[res].merge(u, v), e[res][u].push_back(v), e[res][v].push_back(u);
  }
  printf("%d %d\n", t + 1, s + 1);
  for (int i = 0; i < k; ++i) {
    vector<int> vec;
    auto dfs = [&](auto &self, int u, int fa) -> bool {
      if (u == t) { vec.push_back(t); return 1; }
      for (int v : e[i][u])
        if (v != fa && self(self, v, u)) { vec.push_back(u); return 1; }
      return 0;
    };
    dfs(dfs, s, -1), printf("%d ", (int)vec.size());
    for (int j = 0; j < vec.size(); ++j) printf("%d%c", vec[j] + 1, " \n"[j + 1 == vec.size()]);
  }
}

int main() {
  int T;
  for (scanf("%d", &T); T; --T) solve();
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 58ms
memory: 3832kb

input:

10000
2 20
1 2
1 2
2 1
1 2
1 2
2 1
1 2
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 20
2 1
2 1
2 1
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
1 2
2 20
1 2
2 1
1 2
1 2
2 1
2 1
1 2
1 2
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 1
2 20
1 2
2 1
2 1
1 2
1 2
1 2
2 1
1 2
2 ...

output:

0 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
0 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
0 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
0 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
...

result:

wrong answer Integer 0 violates the range [1, 2] (test case 1)