Submission #804586

#TimeUsernameProblemLanguageResultExecution timeMemory
804586HanksburgerPipes (CEOI15_pipes)C++17
50 / 100
803 ms59288 KiB
#include <bits/stdc++.h> using namespace std; int par[100005][2], tin[100005], low[100005], visited[100005], t; vector<pair<int, int> > ans; vector<int> adj[100005]; int findPar(int u, int x) { return (par[u][x]==u?u:par[u][x]=findPar(par[u][x], x)); } void dfs(int u, int p) { tin[u]=low[u]=(++t); visited[u]=1; int pass=1; for (int v:adj[u]) { if (v==p && pass) { pass=0; continue; } if (visited[v]) low[u]=min(low[u], tin[v]); else { dfs(v, u); low[u]=min(low[u], low[v]); if (low[v]>=tin[v]) ans.push_back({u, v}); } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; for (int i=1; i<=n; i++) par[i][0]=par[i][1]=i; for (int i=1; i<=m; i++) { int u, v, U, V; cin >> u >> v; if (findPar(u, 0)!=findPar(v, 0)) { par[par[u][0]][0]=par[v][0]; adj[u].push_back(v); adj[v].push_back(u); } else if (findPar(u, 1)!=findPar(v, 1)) { par[par[u][1]][1]=par[v][1]; adj[u].push_back(v); adj[v].push_back(u); } } for (int i=1; i<=n; i++) if (!visited[i]) dfs(i, 0); for (int i=0; i<ans.size(); i++) cout << ans[i].first << ' ' << ans[i].second << '\n'; }

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:44:19: warning: unused variable 'U' [-Wunused-variable]
   44 |         int u, v, U, V;
      |                   ^
pipes.cpp:44:22: warning: unused variable 'V' [-Wunused-variable]
   44 |         int u, v, U, V;
      |                      ^
pipes.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i=0; i<ans.size(); i++)
      |                   ~^~~~~~~~~~~
#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...