QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55706#4498. Planar GraphlqhsmashRE 0ms0kbC++1.4kb2022-10-14 22:46:152022-10-14 22:46:16

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-14 22:46:16]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2022-10-14 22:46:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e6 + 20, M = 1e6 + 20;
int n, m;
bool vis[N], vis_line[M];
vector<int> ans;
struct LINE{
    int a, b;
}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++;
}

void dfs(int u, int form){
    vis[u] = true;
    vis_line[form] = true;
    for(int i = h[u]; ~i; i = ne[i]){
        int v = e[i], c = w[i];
        if(c == form || vis_line[c]) continue;
        if(vis[v]) ans.push_back(c);
        dfs(v, c);
    }
}

void slove(){
    for(int i = 1; i <= m; i++){
        int a = line[i].a, b = line[i].b;
        if(!vis[a]) dfs(a, i);
    }
    sort(ans.begin(), ans.end());
    printf("%d\n", (int)ans.size());
    for(auto it: ans){
        printf("%d ", it);
    }
}

void init(){
    ans.clear();
    memset(h, -1, sizeof h);
    memset(vis, 0, sizeof vis);
    memset(vis_line, 0, sizeof vis_line);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        if(a == b){
            ans.push_back(i);
        }
        add(a, b, i);
        add(b, a, i);
        line[i] = {a, b};
    }
}

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
Runtime Error

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 0
0
120314
2 3 4 4 5 5 6 6 7 8 10 10 11 12 12 14 15 15 16 17 19 19 21 22 23 23 26 27 28 29 30 30 31 33 33 34 34 39 39 40 40 42 42 43 45 45 46 47 48 48 52 53 55 56 57 58 59 61 62 63 65 65 66 68 68 69 72 73 74 75 77 78 79 80 83 85 86 86 87 87 88 89 90 91 92 93 94 95 96 96 98 98 100 101 101 103...

result: