Submission #1139706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139706		adelina	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	3094 ms	28640 KiB

menesinis_bilietas

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int Nmax = 5e5 + 5;

vector<pair<int, int>>g[Nmax];
int drum[Nmax];

int n;
void bfs(int nod)
{
    deque<int>de;
    for(int i = 0; i <= n; i ++)
        drum[i] = 1e9;
    drum[nod] = 0;
    de.push_front(nod);
    while(!de.empty())
    {
        nod = de.front();
        de.pop_front();
        for(auto it: g[nod])
            if(drum[nod] + it.second < drum[it.first])
            {
                drum[it.first] = drum[nod] + it.second;
                if(it.second == 0)
                    de.push_front(it.first);
                else
                    de.push_back(it.first);
            }
    }
}

int main()
{
    int m, i, a, b, cntt = 0, cntb = 0, c = 0, ans = 0, j;
    char ch;
    cin >> n >> m;
    for(i = 1; i <= m; i ++)
    {
        cin >> a >> b >> ch;
        if(ch == 'T') c = 0, cntt ++;
        else c = 1, cntb ++;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    if(cntb == 0)
    {
        bfs(1);
        for(i = 1; i <= n; i ++)
            if(drum[i] <= 1)
                ans ++;
        cout << ans;
        return 0;
    }
    if(cntt == 0)
    {
        for(i = 1; i <= n; i ++)
            if(g[i].size() == n - 1)
                ans ++;
        cout << ans;
        return 0;
    }
    for(i = 1; i <= n; i ++)
    {
        bool ok = 1;
        bfs(i);
        for(j = 1; j <= n; j ++)
            if(drum[j] > 1)
            {
                ok = 0;
                break;
            }
        ans += ok;
    }
    cout << ans;
    return 0;
}

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