QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791878 | #995. 桥 | Fire_Raku | WA | 238ms | 41836kb | C++20 | 1.5kb | 2024-11-28 21:35:43 | 2024-11-28 21:35:44 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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