oj.uz

Submission #538351

# Submission time Handle Problem Language Result Execution time Memory
538351 2022-03-16T15:59:51 Z FatihSolak Potemkin cycle (CEOI15_indcyc) C++17
90 / 100
 375 ms 10080 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] && i != par[a][b]){
            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];
                }
                for(auto u:nodes){
                    cout << u << " ";
                }
                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
*/

Subtask #1
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
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 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3052 KB Output is correct
2 Correct 2 ms 2004 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 13 ms 3028 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 8 ms 2728 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 9288 KB Output is correct
2 Correct 23 ms 7380 KB Output is correct
3 Correct 265 ms 10028 KB Output is correct
4 Correct 74 ms 9564 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5644 KB Output is correct
2 Correct 111 ms 8684 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 4420 KB Output is correct
2 Correct 134 ms 4120 KB Output is correct
3 Correct 13 ms 2512 KB Output is correct
4 Correct 375 ms 10080 KB Output is correct