제출 #679932

#제출 시각아이디문제언어결과실행 시간메모리
679932bin9638Potemkin cycle (CEOI15_indcyc)C++17
90 / 100
1088 ms1492 KiB
#include<bits/stdc++.h> using namespace std; #define N 1010 #define ll long long #define ii pair<int,int> #define fs first #define sc second #define pb push_back #define iii pair<int,ii> int n,m,ktr[N]; vector<int>g[N]; bitset<N>bit[N],edge[N]; ii dp[N]; deque<int>dq; struct DSU { int lab[N]; void init() { memset(lab,-1,sizeof(lab)); } int root(int u) { if(lab[u]<0) return u; return(lab[u]=root(lab[u])); } void update(int u,int v) { if((u=root(u))==(v=root(v))) return; if(lab[u]>lab[v]) swap(u,v); lab[u]+=lab[v]; lab[v]=u; } }T; bool clique(bitset<N>bit) { while(bit._Find_first()!=N) { int pos=bit._Find_first(); bit[pos]=0; if((bit|edge[pos])!=bit) return 0; } return 1; } void dijkstra(int S,int T) { // cout<<S<<" "<<T<<endl; for(int i=1;i<=n;i++) dp[i].fs=1e9; dp[S]={0,0}; dq.push_back(S); while(!dq.empty()) { int u=dq.front(); dq.pop_front(); for(auto v:g[u]) if((ktr[v]==0||v==T)&&dp[v].fs>dp[u].fs+1) { dp[v]={dp[u].fs+1,u}; dq.pb(v); } } int i=T; cout<<T<<" "; while(i!=S) { i=dp[i].sc; cout<<i<<" "; } } void solve(int u) { memset(ktr,0,sizeof(ktr)); ktr[u]=1; for(auto v:g[u]) ktr[v]=1; T.init(); for(int i=1;i<=n;i++) if(ktr[i]==0) { for(auto v:g[i]) if(ktr[v]==0) T.update(i,v); } for(int i=1;i<=n;i++) bit[i].reset(); for(int i=1;i<=n;i++) if(ktr[i]==0) { int r=T.root(i); for(auto v:g[i]) if(ktr[v]==1) bit[r][v]=1; } for(int i=1;i<=n;i++) if(T.root(i)==i&&!clique(bit[i])) { for(int l=1;l<=n;l++) for(int r=l+1;r<=n;r++) if(bit[i][l]==1&&bit[i][r]==1&&edge[l][r]==0) { cout<<u<<" "; dijkstra(l,r); exit(0); } } } int main() { // freopen("A.inp","r",stdin); // freopen("A.out","w",stdout); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; for(int i=1;i<=m;i++) { int u,v; cin>>u>>v; g[u].pb(v); g[v].pb(u); edge[u][v]=edge[v][u]=1; } for(int i=1;i<=n;i++) solve(i); cout<<"no"; return 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...