QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515940#2341. Dead-End DetectorRico64AC ✓555ms92548kbC++232.9kb2024-08-12 11:51:332024-08-12 11:51:34

Judging History

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

  • [2024-08-12 11:51:34]
  • 评测
  • 测评结果:AC
  • 用时:555ms
  • 内存:92548kb
  • [2024-08-12 11:51:33]
  • 提交

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