Submission #154232

#TimeUsernameProblemLanguageResultExecution timeMemory
154232arnold518Pipes (CEOI15_pipes)C++14
100 / 100
1781 ms13756 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; struct UF { int par[MAXN+1]; UF() { for(int i=0; i<=MAXN; i++) par[i]=i; } int Find(int x) { if(x==par[x]) return x; return par[x]=Find(par[x]); } void Union(int x, int y) { x=Find(x); y=Find(y); par[x]=y; } }; UF uf1, uf2; int N, M; vector<int> adj[MAXN+1]; int idx[MAXN+1], cnt=1; int dfs(int now, int bef) { idx[now]=cnt++; int ret=idx[now]; int k=0; for(int nxt : adj[now]) { if(nxt==bef) { k++; continue; } if(idx[nxt]!=0) ret=min(ret, idx[nxt]); else { int t=dfs(nxt, now); ret=min(ret, t); if(t>idx[now]) printf("%d %d\n", now, nxt); } } if(k>1) ret=min(ret, idx[bef]); return ret; } int main() { int i, j; scanf("%d%d", &N, &M); while(M--) { int u, v; scanf("%d%d", &u, &v); if(uf1.Find(u)!=uf1.Find(v)) uf1.Union(u, v), adj[u].push_back(v), adj[v].push_back(u); else if(uf2.Find(u)!=uf2.Find(v)) uf2.Union(u, v), adj[u].push_back(v), adj[v].push_back(u); } for(i=1; i<=N; i++) if(idx[i]==0) dfs(i, i); }

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:55:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
pipes.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         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...