oj.uz

Submission #573282

# Submission time Handle Problem Language Result Execution time Memory
573282 2022-06-06T11:06:12 Z vladislav11 Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 401 ms 5568 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1492 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 2 ms 1620 KB Output is correct
4 Correct 18 ms 1624 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1556 KB Output is correct
2 Correct 12 ms 1604 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5068 KB Output is correct
2 Correct 7 ms 4820 KB Output is correct
3 Correct 254 ms 5268 KB Output is correct
4 Correct 99 ms 4808 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4604 KB Output is correct
2 Correct 213 ms 4856 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3276 KB Output is correct
2 Correct 84 ms 3784 KB Output is correct
3 Correct 22 ms 5508 KB Output is correct
4 Correct 401 ms 5568 KB Output is correct