QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#340307 | #995. 桥 | orz_z | WA | 478ms | 60928kb | C++14 | 1.4kb | 2024-02-28 20:54:55 | 2024-02-28 20:54:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define F(i, l, r) for(int i = (l); i <= (r); ++i)
#define dF(i, r, l) for(int i = (r); i >= (l); --i)
int ri() {
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x* 10 + c - 48;
c = getchar();
} return x * f;
}
const int _ = 5e5 + 5;
int tot = 1, head[_], to[_ << 1], nxt[_ << 1];
void add(int u, int v) {
to[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}
int dfn[_], low[_], cnt;
struct node {
pair<int, int> a;
int Id;
};
map<pair<int, int>, node > mp;
vector<node> ans;
void tarjan(int u, int Id = 0) {
dfn[u] = low[u] = ++cnt;
for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i]) {
if(!dfn[v]) {
tarjan(v, i);
low[u] = min(low[u], low[v]);
if(low[v] > low[u]) {
ans.push_back(mp[{u, v}]);
}
} else if(i != (Id ^ 1)) {
low[u] = min(low[u], dfn[v]);
}
}
}
signed main() {
int n = ri(), m = ri();
F(i, 1, m) {
int u = ri(), v = ri();
add(u, v), add(v, u);
mp[{u, v}] = mp[{v, u}] = (node){make_pair(u, v), i};
}
F(i, 1, n) if(!dfn[i]) tarjan(i);
sort(ans.begin(), ans.end(), [&](node a, node b) { return a.Id < b.Id;});
for(node v : ans) {
cout << v.a.first << ' ' << v.a.second << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 478ms
memory: 60928kb
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:
15746 21828 7598 23457 14883 19221 12188 3230 7808 23367 15712 21101 9097 23569 13570 11745 11161 3044 2338 15749 22238 21813 23994 19103 19633 1848 19487 19696 18843 5176 6799 19592 23430 23243 13441 17744 8680 20647 17093 20931 14720 5233 13549 7442 19329 24552 2358 12803 20847 16712 11398 47 1400...
result:
wrong output format Extra information in the output file