QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#378045#2341. Dead-End DetectorUFRJ#AC ✓449ms110196kbC++203.1kb2024-04-05 23:12:532024-04-05 23:12:53

Judging History

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

  • [2024-04-05 23:12:53]
  • 评测
  • 测评结果:AC
  • 用时:449ms
  • 内存:110196kb
  • [2024-04-05 23:12:53]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;
using lint = int64_t;

int main(void) {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin>>n>>m;
    vector<vector<pair<int, int>>>g(n);
    vector<pair<int, int>>e(m);
    for(int i=0;i<m;i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        g[a].emplace_back(b, i);
        g[b].emplace_back(a, i);
        e[i] = {a, b};
    }
    vector<int>h(n), dp(n);
    vector<bool>vis(n), w(m);
    bool is_tree = true;
    auto dfs = [&](auto& self, int u)->void {
        vis[u] = 1;
        for(auto [v, ind] : g[u]){
            if(!vis[v]){
                h[v] = h[u] + 1;
                self(self, v);
                dp[u] += dp[v];
                if(!dp[v]) w[ind] = 1;
                else is_tree = false;
            } 
            else{
                if(h[v] > h[u] + 1) dp[u]--;
                if(h[v] < h[u] - 1) dp[u]++;
            }
        }
    };
    vector<bool>tree(n);
    auto comp_tree = [&](auto& self, int u)->void {
        tree[u] = 1;
        for(auto [v, ind] : g[u]){
            if(tree[v]) continue;
            self(self, v);
        }
    };
    for(int i=0;i<n;i++) if(!vis[i]){
        dfs(dfs, i);
        if(!is_tree){
            is_tree = true;
        }
        else{
            comp_tree(comp_tree, i);
        }
    }
    vector<int>color(n, -1);
    int cur = 0;
    auto dfs2 = [&](auto& self, int u)->void {
        color[u] = cur;
        for(auto [v, ind] : g[u]){
            if(color[v] != -1 || w[ind]) continue;
            self(self, v);
        }
    };
    for(int i=0;i<n;i++) if(color[i] == -1) dfs2(dfs2, i), cur++;
    vector<vector<pair<int, int>>>adj(cur);
    vector<int>cnt(cur);
    for(int i=0;i<n;i++) cnt[color[i]]++;
    vector<int>deg(cur);
    for(int i=0;i<m;i++){
        if(!w[i]) continue; 
        auto [a, b] = e[i];
        adj[color[a]].emplace_back(color[b], i);
        adj[color[b]].emplace_back(color[a], i);
    }
    vector<int>dp2(cur);
    for(int i=0;i<cur;i++) if(cnt[i] > 1) dp2[i] = 1;
    vector<bool>vis2(cur);
    vector<pair<int, int>>ans;

    auto dfs3 = [&](auto& self, int u, int p)->void {
        vis2[u] = 1;
        for(auto [v, ind] : adj[u]){
            if(v == p) continue;
            self(self, v, u);
            dp2[u] += dp2[v];
        }
        if(dp2[u]){
            for(auto [v, ind] : adj[u]){
                if(v == p) continue;
                if(!dp2[v]){
                    auto [a, b] = e[ind];
                    if(color[a] != u) swap(a, b);
                    ans.emplace_back(a, b);
                }
            }
        }
    };
    for(int i=0;i<cur;i++){
        if(dp2[i] && !vis2[i]){
            dfs3(dfs3, i, i);
        }
    }
    for(int i=0;i<n;i++){
        if(tree[i] && g[i].size() == 1){
            auto [j, ind] = g[i][0];
            ans.emplace_back(i, j);
        }
    }
    sort(ans.begin(), ans.end());
    cout<<ans.size()<<"\n";
    for(auto [a, b] : ans) cout<<a+1<<" "<<b+1<<"\n";




    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3608kb

Test #2:

score: 0
Accepted
time: 0ms
memory: 3632kb

Test #3:

score: 0
Accepted
time: 193ms
memory: 71672kb

Test #4:

score: 0
Accepted
time: 0ms
memory: 3844kb

Test #5:

score: 0
Accepted
time: 0ms
memory: 3548kb

Test #6:

score: 0
Accepted
time: 0ms
memory: 3844kb

Test #7:

score: 0
Accepted
time: 0ms
memory: 3768kb

Test #8:

score: 0
Accepted
time: 4ms
memory: 38372kb

Test #9:

score: 0
Accepted
time: 0ms
memory: 3568kb

Test #10:

score: 0
Accepted
time: 0ms
memory: 3624kb

Test #11:

score: 0
Accepted
time: 0ms
memory: 3508kb

Test #12:

score: 0
Accepted
time: 0ms
memory: 3608kb

Test #13:

score: 0
Accepted
time: 38ms
memory: 15376kb

Test #14:

score: 0
Accepted
time: 49ms
memory: 15980kb

Test #15:

score: 0
Accepted
time: 380ms
memory: 85828kb

Test #16:

score: 0
Accepted
time: 232ms
memory: 87556kb

Test #17:

score: 0
Accepted
time: 289ms
memory: 88008kb

Test #18:

score: 0
Accepted
time: 279ms
memory: 88484kb

Test #19:

score: 0
Accepted
time: 0ms
memory: 3620kb

Test #20:

score: 0
Accepted
time: 0ms
memory: 3864kb

Test #21:

score: 0
Accepted
time: 2ms
memory: 4040kb

Test #22:

score: 0
Accepted
time: 81ms
memory: 20988kb

Test #23:

score: 0
Accepted
time: 449ms
memory: 110196kb

Test #24:

score: 0
Accepted
time: 91ms
memory: 105068kb

Test #25:

score: 0
Accepted
time: 375ms
memory: 103244kb

Test #26:

score: 0
Accepted
time: 76ms
memory: 71560kb

Test #27:

score: 0
Accepted
time: 276ms
memory: 71600kb

Test #28:

score: 0
Accepted
time: 280ms
memory: 71568kb

Test #29:

score: 0
Accepted
time: 279ms
memory: 71748kb

Test #30:

score: 0
Accepted
time: 118ms
memory: 76320kb

Test #31:

score: 0
Accepted
time: 204ms
memory: 77976kb

Test #32:

score: 0
Accepted
time: 145ms
memory: 89248kb

Test #33:

score: 0
Accepted
time: 246ms
memory: 89824kb

Test #34:

score: 0
Accepted
time: 351ms
memory: 110152kb

Test #35:

score: 0
Accepted
time: 337ms
memory: 81956kb

Test #36:

score: 0
Accepted
time: 395ms
memory: 85628kb

Test #37:

score: 0
Accepted
time: 431ms
memory: 91644kb

Test #38:

score: 0
Accepted
time: 339ms
memory: 81864kb

Test #39:

score: 0
Accepted
time: 314ms
memory: 78652kb

Test #40:

score: 0
Accepted
time: 279ms
memory: 67648kb

Test #41:

score: 0
Accepted
time: 341ms
memory: 80060kb

Test #42:

score: 0
Accepted
time: 292ms
memory: 64532kb

Test #43:

score: 0
Accepted
time: 265ms
memory: 63488kb

Test #44:

score: 0
Accepted
time: 284ms
memory: 88524kb

Test #45:

score: 0
Accepted
time: 264ms
memory: 89248kb