Submission #146706

#TimeUsernameProblemLanguageResultExecution timeMemory
146706MvCPipes (CEOI15_pipes)C++14
100 / 100
1493 ms16336 KiB
#pragma GCC target("avx2") #pragma GCC optimization("O3") #pragma GCC optimization("unroll-loops") #include<bits/stdc++.h> //#include "boxes.h" #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<62); const int inf=(1<<30); const int nmax=1e5+3; const int mod=1e9+7; using namespace std; int n,m,i,x,y,p[nmax],p1[nmax],sz[nmax],sz1[nmax],fup[nmax],fin[nmax],tin,pr[nmax]; vector<pair<int,int> >a[nmax]; int fnd(int x) { if(p[x]==x)return x; return p[x]=fnd(p[x]); } void uni(int x,int y) { a[x].pb(mkp(y,++tin)); a[y].pb(mkp(x,tin)); x=fnd(x),y=fnd(y); if(sz[x]<sz[y])swap(x,y); sz[x]+=sz[y]; p[y]=x; } int fnd1(int x) { if(p1[x]==x)return x; return p1[x]=fnd1(p1[x]); } void uni1(int x,int y) { a[x].pb(mkp(y,++tin)); a[y].pb(mkp(x,tin)); x=fnd1(x),y=fnd1(y); if(sz1[x]<sz1[y])swap(x,y); sz1[x]+=sz1[y]; p1[y]=x; } void dfs(int x) { fin[x]=fup[x]=++tin; for(int i=0;i<a[x].size();i++) { if(a[x][i].sc==pr[x])continue; if(!fin[a[x][i].fr]) { pr[a[x][i].fr]=a[x][i].sc; dfs(a[x][i].fr); fup[x]=min(fup[x],fup[a[x][i].fr]); if(fup[a[x][i].fr]>fin[x])cout<<x<<" "<<a[x][i].fr<<'\n'; } else fup[x]=min(fup[x],fin[a[x][i].fr]); } } int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); cin>>n>>m; for(i=1;i<=n;i++) { p[i]=i; sz[i]=1; p1[i]=i; sz1[i]=1; } while(m--) { cin>>x>>y; if(fnd(x)!=fnd(y)) { uni(x,y); //cout<<x<<" "<<y<<endl; } else if(fnd1(x)!=fnd1(y)) { uni1(x,y); //cout<<x<<" "<<y<<endl; } } //cout<<endl; for(i=1;i<=n;i++) { if(fin[i])continue; dfs(i); } return 0; }

Compilation message (stderr)

pipes.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
pipes.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
pipes.cpp: In function 'void dfs(int)':
pipes.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].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...