Submission #1139984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139984		c32ardash	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	271 ms	65624 KiB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;

const int NMAX=5e5+5;
vector<int> adjt[NMAX], adja[NMAX], cc[NMAX];
int ntc[NMAX], viz[NMAX], nviz=1, ncc, n, m;

void DFS(int u)
{
    ntc[u]=ncc;
    cc[ncc].push_back(u);
    viz[u]=1;
    for(auto v:adjt[u])
        if(viz[v]!=1)
            DFS(v);
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u, v;
        char ch;
        cin>>u>>v>>ch;
        if(ch=='T')
        {
            adjt[u].push_back(v);
            adjt[v].push_back(u);
        }
        else
        {
            adja[u].push_back(v);
            adja[v].push_back(u);
        }
    }
    for(int i=1;i<=n;i++)
        if(viz[i]!=1)
        {
            ncc++;
            DFS(i);
        }
    int ans=0;
    for(int i=1;i<=ncc;i++)
    {
        int cnt=1;
        nviz++; viz[i]=nviz;
        for(auto u:cc[i])
            for(auto v:adja[u])
                if(viz[ntc[v]]!=nviz)
                {
                    viz[ntc[v]]=nviz;
                    cnt++;
                }
        if(cnt==ncc)
            ans+=cc[i].size();
    }
    cout<<ans;
    return 0;
}

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