QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515940 | #2341. Dead-End Detector | Rico64 | AC ✓ | 555ms | 92548kb | C++23 | 2.9kb | 2024-08-12 11:51:33 | 2024-08-12 11:51:34 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
const int MAX_N = 500000;
using namespace std;
int n;
vector<int> graph[MAX_N + 1];
int parent[MAX_N + 1], depth[MAX_N + 1];
bool trav[MAX_N + 1];
void search0(int v, int& se) {
if (trav[v]) return;
trav[v] = true;
for (int& e : graph[v]) {
if (e == parent[v]) continue;
if (trav[e]) {
se = e;
e = -e;
} else {
parent[e] = v;
depth[e] = depth[v] + 1;
search0(e, se);
}
}
}
bool istree[MAX_N + 1];
int crosscount[MAX_N + 1];
void search1(int v) {
istree[v] = true;
crosscount[v] = 0;
for (const int& e : graph[v]) {
if (e == parent[v]) continue;
if (e < 0) {
istree[v] = false;
if (depth[-e] < depth[v]) crosscount[v]++;
if (depth[-e] > depth[v]) crosscount[v]--;
} else {
search1(e);
istree[v] &= istree[e];
crosscount[v] += crosscount[e];
}
}
}
vector<pair<int,int>> res;
void search2(int v) {
for (const int& e : graph[v]) {
if (e == parent[v]) continue;
if (e < 0) continue;
if (crosscount[e] == 0 && istree[e]) {
res.push_back({v, e});
} else {
search2(e);
}
}
}
void search3(int v) {
if (!trav[v]) return;
trav[v] = false;
for (int& e : graph[v]) {
e = abs(e);
if (!trav[e]) continue;
search3(e);
}
}
void search4(int v) {
int c = 0;
for (const int& e : graph[v]) {
if (e < 0) continue;
if (c == 0) {
c = e;
} else {
c = -1;
}
if (e == parent[v]) continue;
search4(e);
}
if (c > 0) {
res.push_back({v, c});
}
}
int main() {
int m;
cin >> n >> m;
for (int i = 0, f, t; i < m; ++i) {
cin >> f >> t;
graph[f].push_back(t);
graph[t].push_back(f);
}
fill(trav + 1, trav + (n + 1), false);
for (int i = 1; i <= n; ++i) {
if (trav[i]) continue;
parent[i] = 0;
depth[i] = 0;
int se = 0;
int re;
search0(i, se);
// cout << se << endl;
if (se > 0) {
search3(i);
parent[se] = 0;
depth[se] = 0;
search0(se, re);
// for (int j = 1; j <= n; ++j) {
// cout << j << " : ";
// for (const int& e : graph[j]) cout << e << ' '; cout << endl;
// }
search1(se);
search2(se);
} else {
search1(i);
search4(i);
}
}
cout << res.size() << endl;
sort(res.begin(), res.end());
for (const auto& p : res) {
cout << p.first << ' ' << p.second << endl;
}
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 0ms
memory: 7708kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 7720kb
Test #3:
score: 0
Accepted
time: 425ms
memory: 92424kb
Test #4:
score: 0
Accepted
time: 2ms
memory: 7664kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 9840kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 7644kb
Test #7:
score: 0
Accepted
time: 2ms
memory: 9840kb
Test #8:
score: 0
Accepted
time: 6ms
memory: 10468kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 7732kb
Test #10:
score: 0
Accepted
time: 1ms
memory: 7640kb
Test #11:
score: 0
Accepted
time: 1ms
memory: 7804kb
Test #12:
score: 0
Accepted
time: 1ms
memory: 7792kb
Test #13:
score: 0
Accepted
time: 128ms
memory: 13768kb
Test #14:
score: 0
Accepted
time: 128ms
memory: 12340kb
Test #15:
score: 0
Accepted
time: 372ms
memory: 39404kb
Test #16:
score: 0
Accepted
time: 424ms
memory: 44192kb
Test #17:
score: 0
Accepted
time: 436ms
memory: 45520kb
Test #18:
score: 0
Accepted
time: 404ms
memory: 45244kb
Test #19:
score: 0
Accepted
time: 2ms
memory: 9760kb
Test #20:
score: 0
Accepted
time: 2ms
memory: 9848kb
Test #21:
score: 0
Accepted
time: 4ms
memory: 7956kb
Test #22:
score: 0
Accepted
time: 118ms
memory: 19396kb
Test #23:
score: 0
Accepted
time: 553ms
memory: 92452kb
Test #24:
score: 0
Accepted
time: 232ms
memory: 76768kb
Test #25:
score: 0
Accepted
time: 437ms
memory: 74776kb
Test #26:
score: 0
Accepted
time: 252ms
memory: 92492kb
Test #27:
score: 0
Accepted
time: 555ms
memory: 92464kb
Test #28:
score: 0
Accepted
time: 506ms
memory: 92548kb
Test #29:
score: 0
Accepted
time: 527ms
memory: 92420kb
Test #30:
score: 0
Accepted
time: 264ms
memory: 42088kb
Test #31:
score: 0
Accepted
time: 316ms
memory: 41752kb
Test #32:
score: 0
Accepted
time: 303ms
memory: 43652kb
Test #33:
score: 0
Accepted
time: 408ms
memory: 44952kb
Test #34:
score: 0
Accepted
time: 475ms
memory: 76928kb
Test #35:
score: 0
Accepted
time: 400ms
memory: 39928kb
Test #36:
score: 0
Accepted
time: 407ms
memory: 45736kb
Test #37:
score: 0
Accepted
time: 435ms
memory: 53376kb
Test #38:
score: 0
Accepted
time: 374ms
memory: 39912kb
Test #39:
score: 0
Accepted
time: 363ms
memory: 39592kb
Test #40:
score: 0
Accepted
time: 459ms
memory: 51152kb
Test #41:
score: 0
Accepted
time: 329ms
memory: 38360kb
Test #42:
score: 0
Accepted
time: 361ms
memory: 36840kb
Test #43:
score: 0
Accepted
time: 411ms
memory: 37608kb
Test #44:
score: 0
Accepted
time: 436ms
memory: 43664kb
Test #45:
score: 0
Accepted
time: 395ms
memory: 44412kb