제출 #861367

#제출 시각아이디문제언어결과실행 시간메모리
861367Faisal_SaqibPipes (CEOI15_pipes)C++17
30 / 100
772 ms65536 KiB
#include <iostream> #include <algorithm> #include <climits> #include <cmath> #include <map> #include <set> #include <iomanip> #include <vector> using namespace std; const int MAXN=1e5+1; const int LG=17; int pa[MAXN][LG]; int par[MAXN]; int par1[MAXN]; int h[MAXN]; int Up[MAXN]; bool vis[MAXN]; vector<int> ma[MAXN]; int get1(int a) { return ((par1[a]==a)?a:par1[a]=get1(par1[a])); } void join1(int a,int b) { a=get1(a); b=get1(b); if(a!=b) par1[a]=b; } int get(int a) { return ((par[a]==a)?a:par[a]=get(par[a])); } bool join(int a,int b) { int oa=a; int ob=b; a=get(a); b=get(b); if(a!=b) { par[a]=b; return 1; } return 0; } void dfs(int x,int p) { // cout<<x<<' '<<p<<endl; pa[x][0]=p; for(int j=1;j<LG;j++) pa[x][j]=pa[pa[x][j-1]][j-1]; h[x]=h[p]+1; for(auto y:ma[x]) if(y!=p) dfs(y,x); } int lca(int x,int y) { if(h[x]>h[y]) swap(x,y); for(int j=LG-1;j>=0;j--) if(h[x]<=h[pa[y][j]]) y=pa[y][j]; if(x==y) return x; for(int j=LG-1;j>=0;j--) if(pa[x][j]!=pa[y][j]) { x=pa[x][j]; y=pa[y][j]; } return pa[x][0]; } void solve(int x,int p=-1) { vis[x]=1; for(auto y:ma[x]) { if(y!=p) { solve(y,x); } } for(auto y:ma[x]) { if(y!=p) { if(h[Up[x]]>h[Up[y]]) { Up[x]=Up[y]; } if(Up[y]==y) { cout<<x<<' '<<y<<endl; } } } } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,m; cin>>n>>m; for(int i=1;i<=n;i++) par[i]=par1[i]=Up[i]=i; for(int i=0;i<m;i++) { int x,y; cin>>x>>y; if(join(x,y)) { // cout<<"Tree Edge "<<x<<' '<<y<<endl; ma[x].push_back(y); ma[y].push_back(x); } else { // cout<<"Cycle Edge "<<x<<' '<<y<<endl; join1(x,y); } } // cout<<"Tree Input:\n"; for(int i=1;i<=n;i++) if(pa[i][0]==0) dfs(i,i); // cout<<"Cycle Input:"<<endl; for(int y=1;y<=n;y++) { int x=get1(y); // cout<<y<<' '<<x<<endl; int c=lca(x,y); if(h[Up[x]]>h[c]) { Up[x]=c; } if(h[Up[y]]>h[c]) { Up[y]=c; } } // cout<<"Bridge Edges:\n"; for(int i=1;i<=n;i++) if(!vis[i]) solve(i); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

pipes.cpp: In function 'bool join(int, int)':
pipes.cpp:38:6: warning: unused variable 'oa' [-Wunused-variable]
   38 |  int oa=a;
      |      ^~
pipes.cpp:39:6: warning: unused variable 'ob' [-Wunused-variable]
   39 |  int ob=b;
      |      ^~
#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...