Submission #1139330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139330		draguta_mihai	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	370 ms	81868 KiB

menesinis_bilietas

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

const int NMAX = 5e5 + 1;

int n, m;
int cnt, nr;

struct bus
{
    int a, b, tip;
};
bus v[NMAX];
bool viz[NMAX];
int M[NMAX],x[NMAX];


vector<vector<int>>G(NMAX);
vector<set<int>>C(NMAX);

void Read()
{

    int a, b;
    char ch;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {

        cin >> a >> b;
        cin >> ch;
        if(ch == 'A')
        {
            v[++cnt].a = a;
            v[cnt].b = b;
        }
        else
        {
            G[a].push_back(b);
            G[b].push_back(a);
        }
    }

}

void dfs(int idx, int mark)
{
    x[nr]++;
    viz[idx] = 1;
    M[idx] = mark;
    for(auto x : G[idx])
        if(viz[x] == 0)
            dfs(x, mark);
}

void compute_conex_elements()
{
    for(int i = 1; i <= n; i++)
        if(viz[i] == 0)
            dfs(i, ++nr);
}

void create_C()
{
    for(int i = 1; i <= cnt; i++)
    {
        int a = v[i].a,
            b = v[i].b;
        if(M[a] != M[b])
        {
            C[M[a]].insert(M[b]);
            C[M[b]].insert(M[a]);
        }

    }
}

void answer()
{
    int sol = 0;
    for(int i = 1; i <= nr; i++)
    {
        if(C[i].size() == nr - 1)
            sol+=x[i];
    }
    cout << sol;
}

int main()
{
    Read();
    compute_conex_elements();
    create_C();
    answer();
    return 0;
}

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