Submission #873568

#TimeUsernameProblemLanguageResultExecution timeMemory
873568Ghulam_JunaidPipes (CEOI15_pipes)C++17
0 / 100
4 ms6748 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 1; int n, m, h[N], mnh[N], edges, u, v, i, r1, r2, rut, cur, nxt; bool vis[N]; vector<pair<int, int>> g[N]; int root1(int& v){ rut = v; cur = v; while (h[rut]!=-1) rut = h[rut]; while (h[cur]!=rut){ nxt = h[cur]; h[cur] = rut; cur = nxt; } } int root2(int& v){ rut = v; cur = v; while (mnh[rut]!=-1) rut = mnh[rut]; while (mnh[cur]!=rut){ nxt = mnh[cur]; mnh[cur] = rut; cur = nxt; } } void merge1(int& u, int& v){ r1 = root1(v); r2 = root1(u); h[r1] = r2; edges++; g[v].push_back({u, edges}); g[u].push_back({v, edges}); } void merge2(int& u, int& v){ r1 = root2(u); r2 = root2(v); mnh[r1] = r2; edges++; g[v].push_back({u, edges}); g[u].push_back({v, edges}); } void dfs(int& v, pair<int, int> prev = {-1, -1}){ vis[v] = 1; if (prev.first == -1) h[v] = 0; mnh[v] = h[v]; for (auto& [u, id] : g[v]){ if (prev.first == u and prev.second == id) continue; mnh[v] = min(mnh[v], h[u]); if (vis[u]) continue; h[u] = h[v] + 1; dfs(u, {v, id}); mnh[v] = min(mnh[v], mnh[u]); if (mnh[u] >= h[u]) printf("%d %d\n", u, v); } } int main(){ scanf("%d%d", &n, &m); for (i=1; i<=n; i++) h[i] = mnh[i] = -1; for (i=0; i<m; i++){ scanf("%d%d", &u, &v); if (root1(u) != root1(v)) merge1(u, v); else if (root2(u) != root2(v)) merge2(u, v); } for (i=1; i<=n; i++) h[i] = mnh[i] = n + 100; for (v = 1; v <= n; v++) if (!vis[v]) dfs(v); }

Compilation message (stderr)

pipes.cpp: In function 'int root1(int&)':
pipes.cpp:19:1: warning: no return statement in function returning non-void [-Wreturn-type]
   19 | }
      | ^
pipes.cpp: In function 'int root2(int&)':
pipes.cpp:31:1: warning: no return statement in function returning non-void [-Wreturn-type]
   31 | }
      | ^
pipes.cpp: In function 'int main()':
pipes.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~
#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...