QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56005#4498. Planar GraphGalaxyWA 484ms6708kbC++1.3kb2022-10-16 13:50:492022-10-16 13:50:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-16 13:50:52]
  • 评测
  • 测评结果:WA
  • 用时:484ms
  • 内存:6708kb
  • [2022-10-16 13:50:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 20, M = 2e5 + 20;
int n, m, fa[N];
bool vis[M];
struct LINE{
    int u, v, id;
}line[M];

int e[M], ne[M], h[M], w[M], idx;
void add(int u, int v, int c){
    e[idx] = v, ne[idx] = h[u], w[idx] = c, h[u] = idx++;
}

bool cmp(LINE x, LINE y){
    return x.id > y.id;
}

int find(int x){
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

void slove(){
    sort(line + 1, line + m + 1, cmp);
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= m; i++){
        int u = line[i].u, v = line[i].v, id = line[i].id;
        int fau = find(u), fav = find(v);
        if(fau != fav){
            fa[fau] = fav;
            vis[id] = true;
        }
    }
    int cnt = 0;
    for(int i = 1; i <= m; i++){
        if(!vis[i]) cnt++;
    }
    printf("%d\n", cnt);
    for(int i = 1; i <= m; i++){
        if(!vis[i]) printf("%d ", i);
    }
}

void init(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++){
        vis[i] = false;
        int u, v;
        scanf("%d%d", &u, &v);
        line[i] = {u, v, i};
    }
}

int main(){
    int T = 1;
    scanf("%d", &T);
    while(T--){
        init();
        slove();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 484ms
memory: 6708kb

input:

15
5 7
1 1
1 2
1 3
3 4
3 4
2 4
2 5
9 9
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
100000 0
100000 200000
77128 77528
77919 78319
67747 68147
21468 21468
9500 9500
3099 3099
60221 60222
71712 71713
26587 93317
6972 6972
58270 58271
7190 7190
76105 76106
73929 74329
32751 32751
4 5
35248 35648
4492 96872
160...

output:

3
1 2 4 3
1 4 7 0
106620
1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 19 20 21 22 23 26 27 28 29 30 31 33 34 36 39 40 41 42 43 45 46 47 48 52 53 55 56 57 58 59 61 62 63 65 66 68 69 72 73 74 75 77 78 79 80 83 84 85 86 87 88 89 90 91 92 93 94 95 96 98 100 101 103 105 106 107 108 109 110 111 113 114 115 116...

result:

wrong answer 2nd lines differ - expected: '1 2 4', found: '1 2 4 3'