Submission #702944

#	Time	Username	Problem	Language	Result	Execution time	Memory
702944		amirhoseinfar1385	Potemkin cycle (CEOI15_indcyc)	C++17	50 / 100	1088 ms	6272 KiB

indcyc

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+5;
vector<int>adj[maxn],fake[maxn];
int val[maxn],viss[maxn],n,m,mat[maxn][maxn],vis[maxn],visd[maxn],par[maxn];
vector<int>bf;
int cnt=0;
int allv[maxn];

void dfs(int u){
 //   cout<<u<<" "<<visd[u]<<" "<<cnt<<"\n";
    if(visd[u]==1){
        return ;
    }
    val[u]=cnt;
    visd[u]=1;
    for(auto x:fake[u]){
        dfs(x);
    }
}

void solve(int had){
    for(auto x:bf){
        viss[x]=1;
        if(x==had){
            while(x>0){
                cout<<x<<" ";
                x=par[x];
            }
            return ;
        }
    } 
    vector<int>fakea;
    for(auto x:bf){
        for(auto y:fake[x]){
            if(viss[y]==0){
                par[y]=x;
                fakea.push_back(y);
                viss[y]=1;
            } 
        }
    }
    swap(fakea,bf);
    return solve(had);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        mat[u][v]=mat[v][u]=1;
    }
    for(int u=1;u<=n;u++){
        for(int j=1;j<=n;j++){
            fake[j].clear();
            val[j]=0;
            vis[j]=0;
            visd[j]=0;
        }
        vis[u]=1;
        for(auto x:adj[u]){
            vis[x]=1;
        }
        for(int j=1;j<=n;j++){
            if(vis[j]==1){
                continue;
            }
            for(auto x:adj[j]){
                if(vis[x]==1){
                    continue;
                }
                fake[j].push_back(x);
               // cout<<"adj "<<j<<" "<<x<<"\n";
            }
        }
        cnt=0;
        for(int j=1;j<=n;j++){
            if(visd[j]==0){
                cnt++;
                dfs(j);
            }
        } 
        for(int i=0;i<(int)adj[u].size();i++){
            for(int j=i+1;j<(int)adj[u].size();j++){
               // cout<<u<<" "<<adj[u][i]<<" "<<adj[u][j]<<" "<<val[adj[u][i]]<<" "<<val[adj[u][j]]<<"\n";
                if(mat[adj[u][i]][adj[u][j]]==0){
                  //  cout<<"salam"<<endl;
                    for(auto x:adj[adj[u][i]]){
                        if(vis[x]==1){
                            continue;
                        }
                        allv[val[x]]=x;
                    }
                   // cout<<"salam"<<endl;
                    for(auto x:adj[adj[u][j]]){
                        if(allv[val[x]]==0||vis[x]==1){
                            continue;
                        }
              //          cout<<x<<" "<<allv[val[x]]<<endl;
                        bf.push_back(x);
                        solve(allv[val[x]]);
                        cout<<adj[u][j]<<" "<<u<<" "<<adj[u][i]<<"\n";
                        return 0;
                    }
                    for(auto x:adj[adj[u][i]]){
                        allv[val[x]]=0;
                    }
                }
            } 
        } 
    }
    cout<<"no\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10