QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#777866#6421. Degree of Spanning TreeWaterSunWA 37ms4044kbC++142.5kb2024-11-24 10:30:322024-11-24 10:30:33

Judging History

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

  • [2024-11-24 10:30:33]
  • 评测
  • 测评结果:WA
  • 用时:37ms
  • 内存:4044kb
  • [2024-11-24 10:30:32]
  • 提交

answer

#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second

using namespace std;

typedef pair<int,int> pii;
const int N = 2e5 + 10;
int n,m;
int f[N],deg[N];
bool vis[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline int find(int x){
    if (f[x] != x) return f[x] = find(f[x]);
    else return f[x];
}

inline void merge(int a,int b){
    int x = find(a),y = find(b);
    if (x == y) return;
    if (vis[x]) swap(x,y);
    f[x] = y;
}

int tot;

inline void solve(){
    vector<pii> e1,e2;
    n = read(),m = read();
    if ((++tot) == 120) cout << n << " " << m << " nm\n";
    fill(deg + 1,deg + n + 1,0);
    fill(vis + 1,vis + n + 1,false);
    for (re int i = 1;i <= n;i++) f[i] = i;
    for (re int i = 1,a,b;i <= m;i++){
        a = read(),b = read();
        if (find(a) != find(b)){
            merge(a,b);
            deg[a]++; deg[b]++;
            e1.push_back({a,b});
        }
        else e2.push_back({a,b});
    }
    if (tot > 2) return;
    int rt = 0;
    for (re int i = 1;i <= n;i++){
        if (deg[i] > n / 2) rt = i;
    }
    if (!rt){
        puts("Yes");
        for (pii p:e1) printf("%d %d\n",p.fst,p.snd);
        return;
    }
    for (re int i = 1;i <= n;i++) f[i] = i;
    for (pii p:e1){
        if (p.fst == rt) vis[p.snd] = true;
        else if (p.snd == rt) vis[p.fst] = true;
    }
    for (pii p:e1){
        if (p.fst != rt && p.snd != rt) merge(p.fst,p.snd);
    }
    for (pii p:e2){
        if (p.fst != rt && p.snd != rt && find(p.fst) != find(p.snd)){
            if (deg[p.fst] + 1 <= n / 2 && deg[p.snd] + 1 <= n / 2){
                int x = find(p.fst),y = find(p.snd);
                if (deg[x] < deg[y]) swap(x,y);
                deg[x]--; deg[rt]--;
                deg[p.fst]++; deg[p.snd]++;
                vis[x] = false; merge(x,y);
                e1.push_back(p);
            }
        }
    }
    if (deg[rt] > n / 2) puts("No");
    else{
        puts("Yes");
        for (pii p:e1){
            if (p.fst != rt && p.snd != rt) printf("%d %d\n",p.fst,p.snd);
        }
        for (re int i = 1;i <= n;i++){
            if (vis[i]) printf("%d %d\n",rt,i);
        }
    }
}

int main(){
    int T; T = read();
    while (T--) solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3720kb

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
1 2
1 3
1 4
4 5
4 6
No

result:

ok 2 cases

Test #2:

score: -100
Wrong Answer
time: 37ms
memory: 4044kb

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
9 6
5 7
6 5
2 3
3 10
9 1
2 8
4 3
6 2
Yes
3 7
3 9
2 8
3 6
5 1
1 8
8 9
4 8
5 12 nm

result:

wrong answer Line "5 12 nm" doesn't correspond to pattern "Yes|No"