oj.uz

Submission #538356

# Submission time Handle Problem Language Result Execution time Memory
538356 2022-03-16T16:09:34 Z FatihSolak Potemkin cycle (CEOI15_indcyc) C++17
100 / 100
 447 ms 10052 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 1136 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3028 KB Output is correct
2 Correct 3 ms 2004 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 18 ms 3088 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2132 KB Output is correct
2 Correct 7 ms 2772 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 9280 KB Output is correct
2 Correct 24 ms 7380 KB Output is correct
3 Correct 228 ms 10040 KB Output is correct
4 Correct 105 ms 9548 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5588 KB Output is correct
2 Correct 118 ms 8720 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4376 KB Output is correct
2 Correct 136 ms 4144 KB Output is correct
3 Correct 12 ms 2564 KB Output is correct
4 Correct 447 ms 10052 KB Output is correct