Submission #1139760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139760		vladig	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	246 ms	24288 KiB

menesinis_bilietas

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

struct path
{
    int town, way;
};

#define MAXN 500000
#define INF 500001

int n, m;
vector<path> a[ MAXN + 1 ];
int road[ MAXN + 1 ];
bool marked[ MAXN + 1 ];

path formpath( int a, int b )
{
    path d;
    d.town = a, d.way = b;
    return d;
}

void clr( )
{
    for( int i = 0; i <= n; i++ )
    {
        marked[ i ] = 0, road[ i ] = INF;
    }
}

void lee( int start )
{
    clr( );
    deque<int> qu;

    road[ start ] = 0;
    qu.push_back( start );
    marked[ start ] = true;

    while( qu.empty( ) == false )
    {
        int current = qu.front( );
        qu.pop_front( );
        marked[ current ] = false;

        for( auto it: a[ current ] )
        {
            if( road[ current ] + it.way < road[ it.town ] )
            {
                road[ it.town ] = road[ current ] + it.way;

                if( marked[ it.town ] == false )
                {
                    if( it.way == 0 )
                    {
                        qu.push_front( it.town );
                    }
                    else
                    {
                        qu.push_back( it.town );
                    }
                }

                marked[ it.town ] = true;
            }
        }
        //cout << '\n';
    }
}

int main()
{
    cin >> n >> m;

    int notrain, nobus;
    notrain = nobus = 0;

    for( int i = 1; i <= n; i++ )
    {
        int c1, c2;
        char c;

        cin >> c1 >> c2 >> c;
        if( c == 'T' )
        {
            notrain++;
            a[ c1 ].push_back( formpath( c2, 0 ) );
            a[ c2 ].push_back( formpath( c1, 0 ) );
        }
        else
        {
            nobus++;
            a[ c1 ].push_back( formpath( c2, 1 ) );
            a[ c2 ].push_back( formpath( c1, 1 ) );
        }
    }

    lee( 1 );
    int k;
    for( k = 1; k <= n; k++ )
    {
        if( road[ k ] == INF )
        {
            cout << 0;
            return 0;
        }
    }


    if( notrain == 0 )
    {
        int answ = 0;
        for( int i = 1; i <= n; i++ )
        {
            if( a[ i ].size( ) == n - 1 )
            {
                answ++;
            }
        }

        cout << answ;
    }
    else if( nobus == 0 )
    {
        int answ = 0;
        lee( 1 );
        for( int i = 1; i <= n; i++ )
        {
            if( road[ i ] <= 1 )
            {
                answ++;
            }
        }
        cout << answ;
    }
    else
    {
        int answ = 0;
        int work;
        for( int i = 1; i <= n; i++ )
        {
            work = 1;
            lee( i );
            for( int j = 1; j <= n; j++ )
            {
                if( road[ j ] > 1 )
                {
                    work = 0;
                    break;
                }
            }
            answ += work;
        }
        cout << answ;
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 6
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35
• Subtask 5: 0 / 19