Submission #1358236

#TimeUsernameProblemLanguageResultExecution timeMemory
1358236opeleklanosPotemkin cycle (CEOI15_indcyc)C++20
0 / 100
1103 ms98096 KiB
#include <iostream>
#include <vector>
using namespace std;

#define ll long long

vector<vector<int>> adj;
vector<int> depth;
vector<int> maxDepthOfBackEdge;
vector<vector<pair<int, int>>> lift;
vector<int> seen;

void constructTree(int st, int par, int d){
    seen[st] = 1;
    depth[st] = d;
    int mxDepth = -1;

    for(auto c : adj[st]) if(c != par && seen[c] && depth[c]<depth[st]) mxDepth = max(mxDepth, depth[c]);

    maxDepthOfBackEdge[st] = mxDepth;
    if(st!=0){
        lift[st][0] = {max(maxDepthOfBackEdge[st], maxDepthOfBackEdge[par]), par};
        for(int i = 1; i<30; i++){
            lift[st][i].second = lift[lift[st][i-1].second][i-1].second;
            lift[st][i].first = max(lift[st][i-1].first, lift[lift[st][i-1].second][i-1].first);
        }
    }

    for(auto c : adj[st]){
        if(c == par || seen[c]) continue;
        else {
            constructTree(c, st, d+1);
        }
    }


}

int main(void){
    // freopen("input.txt", "r", stdin);
    ll n, m; cin>>n>>m;
    adj.assign(n, {});
    depth.assign(n, 0);
    maxDepthOfBackEdge.assign(n, -1);

    for(ll i = 0; i<m; i++){
        ll a, b; cin>>a>>b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    seen.assign(n, 0);
    lift.assign(n, vector<pair<int, int>>(30, pair<int, int>()));

    lift[0].assign(30, {-1, 0});

    maxDepthOfBackEdge[0] = -1;
    constructTree(0, 0, 0);

    for(int i = 0; i<n; i++){
        int md = maxDepthOfBackEdge[i];
        if(md == -1 || depth[i] - md == 2) continue;
        int mxDe = md - 1;
        int ind = lift[i][0].second;
        int goUp = depth[ind] - md;
        for(int j = 29; j>=0; j--){
            if((1<<j) & goUp){
                mxDe = max(mxDe, lift[ind][j].first);
                ind = lift[ind][j].second;
            }
        }
        if(mxDe >= md) continue;
        else{
            int ind = i;
            while(ind != md){
                cout<<ind + 1<<' ';
                ind = lift[ind][0].second;
            }
            cout<<md + 1<<endl;
            return 0;
        }
    }

    cout<<"no"<<endl;
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...