Submission #1139731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139731		tone_alexandru	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	3093 ms	27128 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, cntt = 0, cnta = 0;
    cin>>n>>m;

    int a, b;
    char type;
    for(int i=0; i<m; i++)
    {
        cin>>a>>b>>type;
        if(type == 'A') cnta ++;
        if(type == 'T') cntt ++;

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

    if(cntt == m) cout<<n;
    else if(cntt == n)
    {
        int cnt = 0;
        for(int i=1; i<=n; i++)
        {
            if(adj[i].size() == n - 1)
                cnt++;
        }
        cout<<cnt;
    }
    else
    {

        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: 0 / 30
• Subtask 4: 0 / 35
• Subtask 5: 0 / 19