Submission #258195

#	Time	Username	Problem	Language	Result	Execution time	Memory
258195		doowey	Potemkin cycle (CEOI15_indcyc)	C++14	80 / 100	1091 ms	2688 KiB

indcyc

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1005;
vector<int> T[N];
int id[N];
int cc;

void dfs(int u){
    id[u]=cc;
    for(auto x : T[u]){
        if(id[x] == -1)
            dfs(x);
    }
}

vector<int> in[N];
bool has[N][N];
int las[N];
int dist[N];
bool mark[N];

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    int u, v;
    for(int i = 0 ; i < m ; i ++ ){
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
        has[u][v] = has[v][u] = true;
    }
    int node;
    int low, xi, yi;
    bool good;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            id[j]=-1;
            in[j].clear();
            mark[j]=false;
        }
        id[i]=0;
        cc=1;
        for(auto x : T[i]){
            mark[x]=true;
            if(id[x] == -1){
                dfs(x);
                cc ++ ;
            }
        }
        for(auto x : T[i]){
            in[id[x]].push_back(x);
        }
        for(int s = 1; s < cc; s ++ ){
            low = (int)1e9, xi = -1, yi = -1;
            good = false;
            for(auto x : in[s]){
                for(auto y : in[s]){
                    if(x==y || has[x][y]) continue;
                    good=true;
                }
            }
            if(!good) continue;
            for(auto x : in[s]){
                queue<int> bf;
                bf.push(x);
                for(int j = 1; j <= n; j ++ ){
                    las[j]=-1;
                    dist[j]=(int)1e9;
                }
                dist[i]=0;
                dist[x] = 0;
                while(!bf.empty()){
                    node = bf.front();
                    bf.pop();
                    if(mark[node] && dist[node] == 1) continue;
                    if(mark[node] && dist[node] > 0){
                        cout << i << " ";
                        while(1){
                            cout << node << " ";
                            if(node == x) break;
                            node = las[node];
                        }
                        return 0;
                    }
                    for(auto f : T[node]){
                        if(dist[f] > dist[node] + 1){
                            dist[f] = dist[node] + 1;
                            las[f] = node;
                            bf.push(f);
                        }
                    }
                }

            }
        }
    }
    cout << "no\n";
    return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:46:9: warning: variable 'low' set but not used [-Wunused-but-set-variable]
     int low, xi, yi;
         ^~~
indcyc.cpp:46:14: warning: variable 'xi' set but not used [-Wunused-but-set-variable]
     int low, xi, yi;
              ^~
indcyc.cpp:46:18: warning: variable 'yi' set but not used [-Wunused-but-set-variable]
     int low, xi, yi;
                  ^~

• 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: 0 / 10
• Subtask 9: 10 / 10
• Subtask 10: 0 / 10