QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#552136#8757. 图caijianhongWA 78ms3612kbC++231.9kb2024-09-07 20:48:212024-09-07 20:48:22

Judging History

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

  • [2024-09-07 20:48:22]
  • 评测
  • 测评结果:WA
  • 用时:78ms
  • 内存:3612kb
  • [2024-09-07 20:48:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
struct dsu {
  vector<int> fa, siz;
  vector<vector<int>> g;
  dsu() = default;
  explicit dsu(int n) : fa(n), siz(n, 1), g(n) { iota(fa.begin(), fa.end(), 0); }
  int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
  bool merge(int x, int y) {
    if (find(x) == find(y)) return false;
    g[x].push_back(y), g[y].push_back(x);
    x = find(x), y = find(y);
    if (siz[x] < siz[y]) swap(siz[x], siz[y]);
    fa[y] = x, siz[x] += siz[y];
    return true;
  }
  vector<int> getpath(int st, int ed) {
    vector<int> stk, ans;
    auto dfs = [&](auto&& dfs, int u, int fa) -> void {
      stk.push_back(u);
      if (ed == u) ans = stk;
      for (int v : g[u]) if (v != fa) dfs(dfs, v, u);
      stk.pop_back();
    };
    dfs(dfs, st, 0);
    return ans;
  }
};
int n, m, k;
int mian() {
  cin >> n >> m;
  k = (m + n - 2) / (n - 1);
  vector<dsu> vec(k, dsu{n});
  int stu = -1, stv;
  for (int i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    --u, --v;
    int l = 0, r = k - 1, ans = k - 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (vec[mid].find(u) == vec[mid].find(v)) l = mid + 1;
      else r = mid - 1, ans = mid;
    }
    vec[ans].merge(u, v);
    if (ans == k - 1) tie(stu, stv) = tie(u, v);
  }
  if (stu == -1) cout << -1 << endl;
  else {
    cout << stu + 1 << " " << stv + 1 << endl;
    for (int i = 0; i < k; i++) {
      auto path = vec[i].getpath(stu, stv);
      cout << path.size();
      for (int x : path) cout << " " << x + 1;
      cout << endl;
    }
  }
  return 0;
}
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);  
#endif
  int t;
  cin >> t;
  while (t--) mian();
  return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 78ms
memory: 3612kb

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:

2 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

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