Submission #948358

#TimeUsernameProblemLanguageResultExecution timeMemory
948358vjudge1Pipes (CEOI15_pipes)C++17
10 / 100
1526 ms65536 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define pb push_back #define ff first #define ss second #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define sz(v) (int)v.size() //const int INF = 1e18; const int mod = 998244353; const int N = 1e5+5; int n; vector<vector<int>> adj; vector<bool> visited; vector<int> tin, low; int timer; map<pair<int,int>,bool> bridge; void IS_BRIDGE(int u, int v){ bridge[{min(u, v), max(u, v)}] = 1; } void dfs(int v, int p = -1) { visited[v] = true; tin[v] = low[v] = timer++; for (int to : adj[v]) { if (to == p) continue; if (visited[to]) { low[v] = min(low[v], tin[to]); } else { dfs(to, v); low[v] = min(low[v], low[to]); if (low[to] > tin[v]) IS_BRIDGE(v, to); } } } void find_bridges() { timer = 0; visited.assign(n, false); tin.assign(n, -1); low.assign(n, -1); for (int i = 0; i < n; ++i) { if (!visited[i]) dfs(i); } } void solve(){ cin >> n; int m; cin >> m; adj.resize(n); for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--; v--; adj[u].pb(v); adj[v].pb(u); } find_bridges(); for(auto [u, v] : bridge) cout << u.ff + 1 << ' ' << u.ss + 1 << '\n'; } main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; while (tt--) { solve(); } }

Compilation message (stderr)

pipes.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main(){
      | ^~~~
#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...