Submission #1139405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139405		mariac	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	665 ms	94032 KiB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;
const int NMAX = 5e5;
int n, m;
vector <pair<int, bool>> graph[NMAX+1];
vector <pair<pair<int, int>, bool>> muchii;
vector <int> componenta(NMAX+1, 0), marime_componenta(NMAX+1, 0), muchii_plecare(NMAX+1, 0);
int id_comp;
map <pair<int , int>, bool> tras;
//bitset <bool> tras[NMAX+1];
void read()
{
    int a, b;
    bool c;
    char ch;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>a>>b>>ch;
        if(ch == 'A') c = 1;
        else c = 0;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
        muchii.push_back({{a, b}, c});
        muchii.push_back({{b, a}, c});
    }
}
void dfs(int node)
{
    componenta[node] = id_comp;
    marime_componenta[id_comp]++;
    for(auto [next, price]:graph[node])
    {
        if(price==0 && componenta[next] == 0)
            dfs(next);
    }
}
void make_comp()
{
    for(int i=1; i<=n; i++)
    {
        if(componenta[i] == 0)
        {
            id_comp++;
            dfs(i);
        }
    }
}
int rez;
void solve()
{
    for(int i=0; i<muchii.size(); i++)
    {
        int a = muchii[i].first.first;
        int b = muchii[i].first.second;
        a = componenta[a];
        b = componenta[b];
        if(a!=b && !(tras.find({a, b})!=tras.end()) )//tras[a][b] == 0)
        {
            tras[{a, b}] = 1;
            //cout<<"din componenta "<<a<<" in "<<b<<'\n';
            muchii_plecare[a]++;
        }
    }
    for(int i=1; i<=id_comp; i++)
    {
        if(muchii_plecare[i] == id_comp-1)
        {
            rez = rez + marime_componenta[i];
        }
    }
}
void debug()
{
    for(int i=1; i<=n; i++)
    {
        cout<<i<<" "<<componenta[i]<<'\n';
    }
}
int main()
{
    read();
    make_comp();
    solve();
    //debug();
    cout<<rez;
    return 0;
}
/*
nodurile conectate prin trenuri sunt componente conexe
-> graf condensat
verific daca pentru fiecare componenta conexa am bus DIRECT catre oricare alta
*/

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