제출 #1139764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139764		vladig	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	46 / 100	3092 ms	31528 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 = 1; i <= n; i++ )
    {
        marked[ i ] = false, 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( int i = 0; i < a[ current ].size( ); i++ )
        {
            path dr = a[ current ][ i ];
            if( road[ current ] + dr.way < road[ dr.town ] )
            {
                road[ dr.town ] = road[ current ] + dr.way;

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

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

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

    int notrain, nobus;
    notrain = nobus = 0;

    for( int i = 1; i <= m; 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;
        bool work;
        for( int i = 1; i <= n; i++ )
        {
            work = true;
            lee( i );
            for( int j = 1; j <= n; j++ )
            {
                if( road[ j ] > 1 )
                {
                    work = false;
                    break;
                }
            }
            answ += work;
        }
        cout << answ;
    }
    return 0;
}

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