QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#791878#995. 桥Fire_RakuWA 238ms41836kbC++201.5kb2024-11-28 21:35:432024-11-28 21:35:44

Judging History

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

  • [2024-11-28 21:35:44]
  • 评测
  • 测评结果:WA
  • 用时:238ms
  • 内存:41836kb
  • [2024-11-28 21:35:43]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii std::pair<int, int>
#define pb push_back
#define mk std::make_pair

using u64 = unsigned long long;
using u32 = unsigned int;
using i64 = long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;
int n, m, tot;
int h[N], cnt = 1;
struct node {
    int frm, to, nxt;
} e[N << 1];
int low[N], dfn[N], cut[N];
std::map<pii, int> mp;
void add(int u, int v) {
    e[++cnt].frm = u;
    e[cnt].to = v;
    e[cnt].nxt = h[u];
    h[u] = cnt;
}
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++tot;
    for(int i = h[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(!dfn[v]) {
            tarjan(v, i);
            if(low[v] > dfn[u]) cut[i] = 1;
            low[u] = std::min(low[u], low[v]);
        } else if(i != (fa ^ 1)) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n >> m;

    for(int i = 1; i <= m; i++) {
        int u, v;
        std::cin >> u >> v;
        mp[mk(u, v)] = 1;
        if(u != v) add(u, v), add(v, u);
    }

    for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i, -1);

    for(int i = 1; i <= cnt; i++) {
        if(cut[i]) {
            if(mp.count(mk(e[i].frm, e[i].to))) std::cout << e[i].frm << " " << e[i].to << "\n";
            else std::cout << e[i].to << " " << e[i].frm << "\n";
        }
    }

    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 238ms
memory: 41836kb

input:

24942 387166
12556 21443
22404 16376
11073 24296
1535 11968
23745 2818
5073 12731
22550 14761
24118 12008
22695 18979
15118 13639
2080 8721
692 22578
22581 15267
9278 4127
7457 21674
17693 23448
10949 23429
9700 6009
14140 5064
7742 15164
17336 1662
18903 9760
17645 19575
6540 11942
11 4937
15282 10...

output:

3207 13717
11313 20267
11313 20267
10188 17964
10188 17964
9883 8907
9883 8907
2127 19115
2127 19115
16876 21570
16876 21570
17835 5637
17835 5637
7653 1997
7653 1997
103 2491
103 2491
3131 10182
3131 10182
6371 5106
6371 5106
3692 16415
3692 16415
21571 23482
21571 23482
16204 21685
16204 21685
189...

result:

wrong output format Extra information in the output file