Submission #1139721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139721		tone_alexandru	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	30 / 100	3095 ms	28452 KiB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, char>> adj[500005];
queue<int> q;

int minim[500005];
signed main()
{
    int n, m;
    cin>>n>>m;

    int a, b;
    char type;
    for(int i=0; i<m; i++)
    {
        cin>>a>>b>>type;

        adj[a].push_back({b, type});
        adj[b].push_back({a, type});
    }

    int cnt = 0;
    for(int i=1; i<=n; i++)
    {
        for(int i=1; i<=n; i++)
            minim[i] = 21e8;
        minim[i] = 0;

        q.push(i);

        while(q.empty() == false)
        {
            int nod = q.front();
            q.pop();

            for(auto x : adj[nod])
            {
                int type = x.second;

                if(type == 'T'&& minim[x.first] > minim[nod])
                {
                    minim[x.first] = minim[nod];
                    q.push(x.first);
                }
                else if(type == 'A' && minim[x.first] > minim[nod] + 1)
                {
                    minim[x.first] = minim[nod] + 1;
                    q.push(x.first);
                }
            }
        }

        int ok = 0;
        for(int j=1; j<=n; j++)
        {
            //cout<<j<<" "<<minim[j]<<'\n';
            if(minim[j] > 1)
            {
                ok = 1;
                //break;
            }
        }

        //cout<<'\n';
        if(ok == 0) cnt++;
    }

    cout<<cnt;


    return 0;
}

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