QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#785378 | #6421. Degree of Spanning Tree | lfyszy | WA | 178ms | 9676kb | C++14 | 2.0kb | 2024-11-26 17:42:46 | 2024-11-26 17:42:51 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define SP << " " <<
#define fish signed
using namespace std;
mt19937 rnd(1209);
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;
vector<pair<int, int>> g;
vector<int> e[N];
int fa[N], fa1[N], d[N];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
set<pair<int, int>> edge;
void dfs(int u, int f)
{
fa1[u] = f; if(f) edge.insert({u, f});
for(auto v : e[u]) if(v != f) dfs(v, u);
}
void solve()
{
int n, m; cin >> n >> m;
for(int i = 1; i <= n; i ++) fa[i] = i, d[i] = 0, e[i].clear();
g.clear(); edge.clear();
for(int i = 1; i <= m; i ++)
{
int u, v; cin >> u >> v;
int fu = find(u), fv = find(v);
if(fu != fv)
{
fa[fu] = fv;
e[u].push_back(v), e[v].push_back(u);
d[u] ++, d[v] ++;
}
else g.push_back({u, v});
}
int rt = 0;
for(int i = 1; i <= n; i ++) if(d[i] > d[rt]) rt = i;
dfs(rt, 0);
for(int i = 1; i <= n; i ++) if(fa1[i] != rt) fa[i] = fa1[i]; else fa[i] = i;
for(auto x : g)
{
if(d[rt] <= n / 2) break;
int u = x.first, v = x.second;
int fu = find(u), fv = find(v);
if(fu == fv) continue;
if(d[fu] > d[fv]) swap(fu, fv), swap(u, v);
if(d[u] + 1 > n / 2 || d[v] + 1 > n / 2) continue;
edge.erase({fv, rt});
edge.insert({v, u});
fa[fv] = fu;
d[u] ++, d[v] ++, d[fv] --, d[rt] --;
}
rt = 0;
for(int i = 1; i <= n; i ++) if(d[i] > d[rt]) rt = i;
if(d[rt] <= n / 2)
{
cout << "Yes\n";
assert(edge.size() <= n - 1);
for(auto v : edge) cout << v.first SP v.second << "\n";
}
else cout << "No\n";
}
fish main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t --) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 8240kb
input:
2 6 9 1 2 1 3 1 4 2 3 2 4 3 4 4 5 4 6 4 6 3 4 1 3 2 3 3 3 1 2
output:
Yes 2 1 3 1 4 1 5 4 6 4 No
result:
ok 2 cases
Test #2:
score: -100
Wrong Answer
time: 178ms
memory: 9676kb
input:
11140 10 15 9 6 5 7 6 5 2 3 7 5 7 5 3 10 9 7 5 5 9 1 7 5 2 8 7 5 4 3 6 2 9 19 3 7 3 9 2 8 2 8 3 6 5 1 1 8 8 9 8 3 4 8 5 5 3 1 4 3 1 3 8 6 1 3 7 4 4 3 8 8 12 20 10 2 5 5 2 4 3 3 3 3 5 11 9 2 5 5 7 12 11 3 3 3 3 5 5 3 3 1 4 6 7 11 6 8 4 5 6 12 6 5 8 18 4 2 4 3 2 4 2 4 4 3 4 8 2 2 6 7 2 4 6 2 1 4 8 7 4...
output:
Yes 1 9 3 2 4 3 5 6 6 2 7 5 8 2 9 6 10 3 Yes 1 8 2 8 3 9 4 8 5 1 6 3 7 3 9 8 Yes 1 3 3 11 4 2 5 4 6 4 7 11 8 6 9 2 10 2 11 5 12 7 Yes 1 4 2 4 3 4 5 7 6 2 7 6 8 4 Yes 1 5 2 9 3 2 4 3 6 5 7 5 8 7 9 5 Yes 1 6 3 2 4 6 5 2 6 2 7 1 8 10 9 1 10 2 Yes 1 7 2 6 3 1 4 5 5 7 6 7 Yes 2 6 3 12 4 1 5 4 6 1 7 8 8 2...
result:
wrong answer case 120, participant does not find a solution but the jury does