Submission #878729

#TimeUsernameProblemLanguageResultExecution timeMemory
878729Ghulam_JunaidPipes (CEOI15_pipes)C++17
10 / 100
1006 ms65536 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m, p, h[N], mnh[N], st[N], ft[N], tme; bool vis[N]; vector<pair<int, int>> g[N], edges, important; string s; bool in_sub(int u, int v){ return (st[v] <= st[u] && st[u] < ft[v]); } void dfs(int v, int prev = -1){ vis[v] = 1; mnh[v] = h[v]; st[v] = tme; tme++; // cout << "Running dfs on " << v << endl; for (auto [id, u] : g[v]){ if (id == prev) continue; if (!vis[u]){ h[u] = h[v] + 1; dfs(u, id); mnh[v] = min(mnh[v], mnh[u]); if (mnh[u] > h[v]){ // (v, u) is a bridge cout << u << " " << v << endl; // cout << v << " -- " << u << " is a bridge." << endl; // for (auto [x, y] : important){ // bool A = in_sub(x, u); // bool B = in_sub(y, u); // // cout << x << " " << y << " " << u << " " << A << " " << B << endl; // if (A and !B){ // // u to v // if (edges[id].first == u) // s[id] = 'R'; // else // s[id] = 'L'; // } // if (!A and B){ // // v to u // if (edges[id].first == v) // s[id] = 'R'; // else // s[id] = 'L'; // } // } } // else // s[id] = 'B'; } else mnh[v] = min(mnh[v], h[u]); } ft[v] = tme; } int main(){ cin >> n >> m; for (int i=0; i<m; i++){ int u, v; cin >> u >> v; s += 'B'; edges.push_back({u, v}); // if (u == v) // continue; g[u].push_back({i, v}); g[v].push_back({i, u}); } // cin >> p; // for (int i=0; i<p; i++){ // int u, v; // cin >> u >> v; // // if (u == v) continue; // important.push_back({u, v}); // } dfs(1); // cout << s << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...