Submission #1139349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139349		ansedra	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	1054 ms	98580 KiB

menesinis_bilietas

#include <iostream>
#include <vector>
#include <map>

using namespace std;

const int Nmax = 500005;

struct nod{
    int componenta;
    vector<int> vecini_tren;
};

struct muchie{
    int nod1, nod2;
};

struct comp{
    int cate_orase;
    int cate_orase_atinge;
};

int n, m, ind_componenta, sol;
nod orase[Nmax];
comp componenta[Nmax];
vector<muchie> muchii_autobus;
map<pair<int, int>, bool> unite;

void citire(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int nod1, nod2;
    char tip;

    cin >> n >> m;

    for(int i = 1; i <= m; i++){
        cin >> nod1 >> nod2 >> tip;

        if(tip == 'T'){
            orase[nod1].vecini_tren.push_back(nod2);
            orase[nod2].vecini_tren.push_back(nod1);
        }
        else{
            muchii_autobus.push_back({nod1, nod2});
        }
    }
}

void dfs(int nod){
    orase[nod].componenta = ind_componenta;
    componenta[ind_componenta].cate_orase++;

    for(int vecin : orase[nod].vecini_tren){
        if(!orase[vecin].componenta){
            dfs(vecin);
        }
    }
}

void procesare_componente_conexe(){
    ind_componenta = 0;
    for(int i = 1; i <= n; i++){
        if(!orase[i].componenta){
            ind_componenta++;
            dfs(i);
        }
    }
}

void procesare_muchii_autobuz(){
    for(int i = 1; i <= ind_componenta; i++){
        unite[{i, i}] = 1;
        componenta[i].cate_orase_atinge = componenta[i].cate_orase;
    }

    for(muchie edge : muchii_autobus){
        if(!unite[{orase[edge.nod1].componenta, orase[edge.nod2].componenta}]){
            componenta[orase[edge.nod1].componenta].cate_orase_atinge += componenta[orase[edge.nod2].componenta].cate_orase;
            componenta[orase[edge.nod2].componenta].cate_orase_atinge += componenta[orase[edge.nod1].componenta].cate_orase;

            unite[{orase[edge.nod1].componenta, orase[edge.nod2].componenta}] = 1;
            unite[{orase[edge.nod2].componenta, orase[edge.nod1].componenta}] = 1;
        }
    }

    sol = 0;
    for(int i = 1; i <= ind_componenta; i++){
        if(componenta[i].cate_orase_atinge == n){
            sol += componenta[i].cate_orase;
        }
    }
}

void afisare_solutie(){
    cout << sol;
}

int main(){
    citire();
    procesare_componente_conexe();
    procesare_muchii_autobuz();
    afisare_solutie();

    return 0;
}

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