QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#448292 | #8757. 图 | propane | WA | 53ms | 3576kb | C++20 | 2.2kb | 2024-06-19 15:17:19 | 2024-06-19 15:17:20 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
using namespace std;
using LL = long long;
struct DSU{
vector<int> p;
DSU(int n) : p(n + 1){
iota(p.begin(), p.end(), 0);
}
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y){
x = find(x), y = find(y);
if (x == y) return false;
p[y] = x;
return true;
}
};
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n, m;
cin >> n >> m;
int k = (m + n - 2) / (n - 1);
vector<DSU> dsu(k, DSU(n));
int p1 = -1, p2 = -1;
vector<vector<vector<int> > > g(k, vector<vector<int> >(n + 1));
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
if (p1 != -1) continue;
int l = 0, r = k;
while(l < r){
int mid = (l + r) / 2;
if (!dsu[mid].same(a, b)) r = mid;
else l = mid + 1;
}
if (r < k){
dsu[r].merge(a, b);
g[r][a].push_back(b);
g[r][b].push_back(a);
}
if (r >= k - 1){
p1 = a, p2 = b;
}
}
vector<int> v(n + 1, -1);
cout << p1 << ' ' << p2 << '\n';
for(int i = 0; i < k; i++){
vector<int> path, ans;
auto dfs = [&](auto &&dfs, int u) -> void {
v[u] = i;
path.push_back(u);
if (u == p2) ans = path;
for(auto j : g[i][u]){
if (v[j] != i){
dfs(dfs, j);
}
}
path.pop_back();
};
dfs(dfs, p1);
for(auto x : ans) cout << x << ' ';
cout << '\n';
}
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 53ms
memory: 3576kb
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 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1...
result:
FAIL Begin in s. (test case 1)