Submission #573282

#	Time	Username	Problem	Language	Result	Execution time	Memory
573282		vladislav11	Potemkin cycle (CEOI15_indcyc)	C++14	100 / 100	401 ms	5568 KiB

indcyc

#include <bits/stdc++.h>

using namespace std;

int n, r;
int adj[1010][1010];
vector< vector<int> > grp;
vector< set<int> > cmp_list;
vector<int> valid, cmp;
int cnt_cmp;

void dfs_cmp ( int v, int numberof )
{
    cmp[v] = numberof;

    for ( auto& to : grp[v] )
    if ( valid[to] == 2 && cmp[to] == -1 )
        dfs_cmp( to, numberof );
}

vector<int> pre;

void bfs_ans ( int st, int fn )
{
    queue<int> q;
    q.push( st );
    pre[st] = -2;

    while ( q.size() )
    {
        int v = q.front();
        q.pop();

        for ( auto& to : grp[v] )
        if ( valid[to] == 2 && pre[to] == -1 )
        {
            pre[to] = v;
            q.push( to );
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> r;

    grp.assign( n+1, vector<int>() );

    for ( int i=0; i<r; i++ )
    {
        int u, v;
        cin >> u >> v;

        grp[u].push_back( v );
        grp[v].push_back( u );

        adj[u][v] = adj[v][u] = 1;
    }

    for ( int root = 1; root <= n; root++ )
    {
        valid.assign( n+1, 2 );

        valid[root] = 0;

        for ( auto& to : grp[root] )
            valid[to] = 1;

        cmp.assign( n+1, -1 );
        cnt_cmp = 0;
        cmp_list.clear();

        for ( int i=1; i<=n; i++ )
        if ( valid[i] == 2 && cmp[i] == -1 )
        {
            cmp_list.push_back({});
            dfs_cmp( i, cnt_cmp++ );
        }

        for ( auto& to : grp[root] )
        {
            for ( auto& to2 : grp[to] )
            if ( to2 != root && valid[to2] == 2 )
                cmp_list[ cmp[to2] ].insert( to );
        }

        int resu = -1, resv = -1;

        for ( int i=0; i<cnt_cmp; i++ )
        {
            for ( auto& u : cmp_list[i] )
            {
                for ( auto& v : cmp_list[i] )
                if ( u != v && !adj[u][v] )
                {
                    resu = u, resv = v;
                    break;
                }

                if ( resu != -1 ) break;
            }

            if ( resu != -1 ) break;
        }

        if ( resu != -1 )
        {
            cout << root << ' ';

            valid[resu] = valid[resv] = 2;

            pre.assign( n+1, -1 );

            bfs_ans( resu, resv );

            vector<int> path;
            path.push_back( resv );

            while ( resv != resu )
            {
                resv = pre[resv];
                path.push_back( resv );
            }

            reverse( path.begin(), path.end() );

            for ( auto& el : path )
                cout << el << ' ';

            cout << '\n';

            return 0;
        }
    }

    cout << "no\n";

    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