oj.uz

Submission #739057

# Submission time Handle Problem Language Result Execution time Memory
739057 2023-05-09T19:56:42 Z kirakaminski968 Potemkin cycle (CEOI15_indcyc) C++17
100 / 100
 325 ms 9624 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
bool edges[MAXN][MAXN]; int vis[MAXN][MAXN],N,parent[MAXN][MAXN];
vector<pair<int,int>> paths;
void dfs(int start, int ed){
    vis[start][ed] = 1;
    for(int i = 1;i<=N;++i){
        if(i == start || vis[ed][i] == 2 || edges[start][i] || !edges[i][ed]) continue;
        if(vis[ed][i]){
            vector<int> cycle; cycle.push_back(ed); cycle.push_back(start);
            while(start != i){
                cycle.push_back(parent[start][ed]);
                int tmp = parent[start][ed];
                ed = start; start = tmp;
            }
            int x = cycle.size();
            int left = 0, right = x-1;
            for(int j = 0;j<x;++j){
                for(int k = j+2;k<x;++k){
                    if(edges[cycle[j]][cycle[k]] && (k-j < right-left)){
                        left = j; right = k;
                    }
                }
            }
            for(int j = left; j<=right;++j) cout << cycle[j] << " ";
            //cout << i << "\n";
            exit(0);
        }
        else{
            parent[ed][i] = start;
            dfs(ed,i);
        }
    }
    vis[start][ed] = 2;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int R; cin >> N >> R;
    for(int i = 0;i<R;++i){
        int a,b; cin >> a >> b;
        edges[a][b] = edges[b][a] = true;
        paths.push_back({a,b});
    }
    for(auto e : paths){
        if(!vis[e.first][e.second]){
            dfs(e.first,e.second);
        }
    }
    cout << "no";
    return 0;
}

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 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 852 KB Output is correct
2 Correct 2 ms 960 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 4 ms 2644 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 14 ms 2916 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 8744 KB Output is correct
2 Correct 31 ms 7224 KB Output is correct
3 Correct 172 ms 9624 KB Output is correct
4 Correct 65 ms 9364 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5960 KB Output is correct
2 Correct 73 ms 7336 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2092 KB Output is correct
2 Correct 109 ms 3284 KB Output is correct
3 Correct 11 ms 2028 KB Output is correct
4 Correct 325 ms 9544 KB Output is correct