oj.uz

Submission #658179

# Submission time Handle Problem Language Result Execution time Memory
658179 2022-11-12T10:45:25 Z blaze21 Potemkin cycle (CEOI15_indcyc) C++17
100 / 100
 250 ms 9980 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>
#include <iomanip>
using namespace std;

#define pi pair<int, int>
#define f first
#define s second

int n;
int par[1005][1005], visited[1005][1005];
bool edge[1005][1005];
 
void dfs(int a, int b){

    //cout << "wut\n";

    visited[a][b] = 1;
    //cout << a << " " << b << endl;

    for(int i = 1; i <= n; i++){

        if(i == a || edge[a][i] || !edge[b][i]){

            //cout << i << endl;
            continue;
        }

        //cout << b << " " << i << endl;

        if(visited[b][i] == 1){

            vector <int> cycle;
            cycle.push_back(b);
            cycle.push_back(a);

            while(a != i){

                cycle.push_back(par[a][b]);
                int tmp = par[a][b];
                b = a;
                a = tmp;
            }

            int sz = cycle.size();
            int l = 0, r = sz - 1;

            for(int j = 0; j < sz; j++){

                for(int k = j + 2; k < sz; k++){

                    if(edge[cycle[j]][cycle[k]]){

                        if(r - l > k - j){

                            l = j;
                            r = k;
                        }
                    }
                }
            }

            for(int j = l; j <= r; j++){

                cout << cycle[j] << " ";
            }

            cout << endl;

            exit(0);
        }

        else if(!visited[b][i]){

            par[b][i] = a;
            dfs(b, i);
        }
    }

    visited[a][b] = 2;
}
 
int main(){
 
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int r;
    cin >> n >> r;

    vector <pi> edges;

    while(r--){

        int a, b;
        cin >> a >> b;

        edge[a][b] = true;
        edge[b][a] = true;
        edges.push_back({a, b});
    }

    for(pi i : edges){

        if(!visited[i.f][i.s]){

            //cout << endl;

            dfs(i.f, i.s);
        }
    }

    cout << "no\n";
}

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 1 ms 328 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 1 ms 340 KB Output is correct
2 Correct 1 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 1 ms 852 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3028 KB Output is correct
2 Correct 4 ms 2772 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 8 ms 3028 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1868 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 87 ms 9132 KB Output is correct
2 Correct 21 ms 7324 KB Output is correct
3 Correct 121 ms 9968 KB Output is correct
4 Correct 44 ms 9556 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6104 KB Output is correct
2 Correct 50 ms 7616 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2780 KB Output is correct
2 Correct 56 ms 4076 KB Output is correct
3 Correct 13 ms 2516 KB Output is correct
4 Correct 250 ms 9980 KB Output is correct