Submission #739057

#	Time	Username	Problem	Language	Result	Execution time	Memory
739057		kirakaminski968	Potemkin cycle (CEOI15_indcyc)	C++17	100 / 100	325 ms	9624 KiB

indcyc

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