Submission #658179

#	Time	Username	Problem	Language	Result	Execution time	Memory
658179		blaze21	Potemkin cycle (CEOI15_indcyc)	C++17	100 / 100	250 ms	9980 KiB

indcyc

#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 / 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