Submission #948792

#TimeUsernameProblemLanguageResultExecution timeMemory
948792AiperiiiPipes (CEOI15_pipes)C++14
50 / 100
2784 ms30288 KiB
#include <bits/stdc++.h> //#define int long long #define ff first #define ss second #define pb push_back #define all(x) x.begin(),x.end() using namespace std; const int N=1e5+5; int p[2][N],tin[N],low[N]; vector <int> g[N]; int find_set(int i,int v){ if(p[i][v]==v)return v; return p[i][v]=find_set(i,p[i][v]); } bool union_set(int i,int u,int v){ if(find_set(i,u)==find_set(i,v))return false; p[i][u]=v; return true; } int t=0,to; void dfs(int v,int par){ t++; p[0][v]=t; p[1][v]=t; bool ok=0; for(int to : g[v]){ if(par==to && !ok)ok=1; else if(p[0][to])p[1][v]=min(p[1][v],p[0][to]); else{ dfs(to,v); p[1][v]=min(p[1][v],p[1][to]); if(p[1][to]>p[0][v]){ cout<<v<<" "<<to<<"\n"; } } } } signed main(){ ios_base::sync_with_stdio(); cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; int i; for(i=1;i<=n;i++){ p[0][i]=i; p[1][i]=i; } int u,v; for(i=0;i<m;i++){ cin>>u>>v; if(union_set(0,u,v)){ g[u].pb(v); g[v].pb(u); } else if(union_set(1,u,v)){ g[u].pb(v); g[v].pb(u); } } for(i=0;i<=n;i++){ p[0][i]=0; p[1][i]=0; } for(i=1;i<=n;i++){ if(!p[0][i])dfs(i,0); } }
#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...