QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363445 | #2341. Dead-End Detector | TWTP_TCTF# | AC ✓ | 691ms | 223260kb | C++14 | 3.5kb | 2024-03-23 22:38:24 | 2024-03-23 22:38:25 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5 + 5, mod = 1e9 + 7;
vector<int> adj[N], bridge_tree[N], nodes_of_color[N], bridges_tal3a[N];
int dfsn[N], low[N], cost[N], timer, cnt, comp_id[N], comp_sz[N], subtree_total[N], kam[N], color[N], in[N];
stack<int> st;
map<pair<int, int>, bool> mark;
vector<pair<int, int>> ans;
void dfs(int node, int par, int c){
nodes_of_color[c].push_back(node);
color[node] = c;
dfsn[node] = low[node] = ++timer;
st.push(node);
for(auto i: adj[node]){
if(i == par) continue;
if(dfsn[i] == 0){
dfs(i, node, c);
low[node] = min(low[node], low[i]);
}
else low[node] = min(low[node], dfsn[i]);
}
if(dfsn[node] == low[node]){
cnt++;
while(1){
int cur = st.top();
st.pop();
comp_id[cur] = cnt;
comp_sz[cnt]++;
if(cur == node) break;
}
}
}
void dfs2(int x, int par){
subtree_total[x] = comp_sz[x] > 1;
for(auto &y: bridge_tree[x]){
if(y == par)
continue;
mark[{x, y}] = true;
dfs2(y, x);
subtree_total[x] += subtree_total[y];
}
}
void solve(int c){
for(auto &i: nodes_of_color[c]){
for(auto j: adj[i]){
if(comp_id[i] != comp_id[j]){
bridge_tree[comp_id[i]].push_back(comp_id[j]);
}
}
}
int root = comp_id[nodes_of_color[c][0]];
dfs2(root, -1);
int total = subtree_total[root];
for(auto &i: nodes_of_color[c]){
for(auto j: adj[i]){
if(comp_id[i] != comp_id[j]){
if(mark[{comp_id[i], comp_id[j]}]){
if(subtree_total[comp_id[j]] == 0){
// critical
bridges_tal3a[i].push_back(j);
in[j]++;
}
if(total - subtree_total[comp_id[j]] == 0){
// critical
bridges_tal3a[j].push_back(i);
in[i]++;
}
}else{
continue;
}
}
}
}
for(auto &i: nodes_of_color[c]){
if(in[i] == 0){
for(auto &j: bridges_tal3a[i])
ans.push_back({i, j});
}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n, m;
cin >> n >> m;
while(m--){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int node = 1, c = 1; node <= n; node++){
if(color[node] == 0){
dfs(node, 0, c);
bool is_tree = true;
for(auto &cur_node: nodes_of_color[c]){
is_tree &= comp_sz[comp_id[cur_node]] == 1;
}
if(is_tree){
for(auto &cur_node: nodes_of_color[c]){
if(adj[cur_node].size() == 1)
ans.push_back({cur_node, adj[cur_node][0]});
}
}else{
solve(c);
}
c++;
}
}
sort(ans.begin(), ans.end());
if(ans.size() == 0){
cout << 0;
}else{
cout << ans.size() << '\n';
for(auto &p: ans)
cout << p.first << ' ' << p.second << '\n';
}
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 3ms
memory: 60624kb
Test #2:
score: 0
Accepted
time: 7ms
memory: 62004kb
Test #3:
score: 0
Accepted
time: 199ms
memory: 130800kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 59684kb
Test #5:
score: 0
Accepted
time: 7ms
memory: 59840kb
Test #6:
score: 0
Accepted
time: 7ms
memory: 61300kb
Test #7:
score: 0
Accepted
time: 4ms
memory: 60632kb
Test #8:
score: 0
Accepted
time: 29ms
memory: 76076kb
Test #9:
score: 0
Accepted
time: 7ms
memory: 61264kb
Test #10:
score: 0
Accepted
time: 7ms
memory: 61112kb
Test #11:
score: 0
Accepted
time: 7ms
memory: 59012kb
Test #12:
score: 0
Accepted
time: 8ms
memory: 61176kb
Test #13:
score: 0
Accepted
time: 47ms
memory: 65400kb
Test #14:
score: 0
Accepted
time: 53ms
memory: 65880kb
Test #15:
score: 0
Accepted
time: 236ms
memory: 83776kb
Test #16:
score: 0
Accepted
time: 191ms
memory: 88160kb
Test #17:
score: 0
Accepted
time: 545ms
memory: 173000kb
Test #18:
score: 0
Accepted
time: 543ms
memory: 173224kb
Test #19:
score: 0
Accepted
time: 8ms
memory: 61828kb
Test #20:
score: 0
Accepted
time: 4ms
memory: 60972kb
Test #21:
score: 0
Accepted
time: 7ms
memory: 61876kb
Test #22:
score: 0
Accepted
time: 97ms
memory: 75596kb
Test #23:
score: 0
Accepted
time: 691ms
memory: 192924kb
Test #24:
score: 0
Accepted
time: 82ms
memory: 129212kb
Test #25:
score: 0
Accepted
time: 269ms
memory: 126116kb
Test #26:
score: 0
Accepted
time: 82ms
memory: 132092kb
Test #27:
score: 0
Accepted
time: 277ms
memory: 130656kb
Test #28:
score: 0
Accepted
time: 240ms
memory: 131732kb
Test #29:
score: 0
Accepted
time: 285ms
memory: 132216kb
Test #30:
score: 0
Accepted
time: 98ms
memory: 92900kb
Test #31:
score: 0
Accepted
time: 222ms
memory: 90560kb
Test #32:
score: 0
Accepted
time: 107ms
memory: 85848kb
Test #33:
score: 0
Accepted
time: 212ms
memory: 86748kb
Test #34:
score: 0
Accepted
time: 674ms
memory: 223260kb
Test #35:
score: 0
Accepted
time: 240ms
memory: 84076kb
Test #36:
score: 0
Accepted
time: 228ms
memory: 90460kb
Test #37:
score: 0
Accepted
time: 234ms
memory: 99892kb
Test #38:
score: 0
Accepted
time: 227ms
memory: 86164kb
Test #39:
score: 0
Accepted
time: 216ms
memory: 87108kb
Test #40:
score: 0
Accepted
time: 365ms
memory: 127040kb
Test #41:
score: 0
Accepted
time: 551ms
memory: 171372kb
Test #42:
score: 0
Accepted
time: 376ms
memory: 126692kb
Test #43:
score: 0
Accepted
time: 396ms
memory: 128032kb
Test #44:
score: 0
Accepted
time: 505ms
memory: 172376kb
Test #45:
score: 0
Accepted
time: 535ms
memory: 172668kb