Submission #538356

#	Time	Username	Problem	Language	Result	Execution time	Memory
538356		FatihSolak	Potemkin cycle (CEOI15_indcyc)	C++17	100 / 100	447 ms	10052 KiB

indcyc

#include <bits/stdc++.h>
#define N 1005
using namespace std;
int vis[N][N];
bool adj[N][N];
int par[N][N];
int n;
void dfs(int a,int b){
    vis[a][b] = 1;
    //cout << a << " " << b << endl;
    for(int i=1;i<=n;i++){
        if(i != a && adj[b][i] && !adj[a][i]){
            if(vis[b][i] == 1){
                vector<int> nodes;
                int st = b;
                nodes.push_back(b);
                nodes.push_back(a);
                while(par[a][b] != st){
                    nodes.push_back(par[a][b]);
                    int tmp = b;
                    b = a;
                    a = par[a][tmp];
                }
                int l = 0,r = nodes.size()-1;
                for(int i = 0;i<nodes.size();i++){
                    for(int j = i+2;j<nodes.size();j++){
                        if(adj[nodes[i]][nodes[j]] && j - i < r - l){
                            l = i;
                            r = j;
                        }
                    }
                }
                for(int i=l;i<=r;i++){
                    cout << nodes[i] << " ";
                }
                exit(0);
            }
            else if(!vis[b][i]){
                par[b][i] = a;  
                dfs(b,i);
            }
        }
    }
    vis[a][b] = 2;
}
void solve(){
    int m;
    cin >> n >> m;
    vector<pair<int,int>> edges;
    for(int i=1;i<=m;i++){
        int a,b;
        cin >> a >> b;
        adj[a][b] = adj[b][a] = 1;
        edges.push_back({a,b});
        edges.push_back({b,a});
    }
    for(auto u:edges){
        if(!vis[u.first][u.second]){
            dfs(u.first,u.second);
        }
    }
    cout << "no";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef Local
        cout << endl << fixed << setprecision(2) << 1000.0 * clock() / CLOCKS_PER_SEC << " milliseconds.";
    #endif
}
/*
14 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 1
4 11
*/

Compilation message (stderr)

indcyc.cpp: In function 'void dfs(int, int)':
indcyc.cpp:25:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |                 for(int i = 0;i<nodes.size();i++){
      |                               ~^~~~~~~~~~~~~
indcyc.cpp:26:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |                     for(int j = i+2;j<nodes.size();j++){
      |                                     ~^~~~~~~~~~~~~

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