Submission #1142466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142466		ionutza	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	273 ms	40156 KiB

menesinis_bilietas

#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

int nodes, edges, numComp, numBuses;
vector <int> graph[500005], graphBuses[500005];
pair <int, int> buses[500005];
set <int> frecv;
int comp[500005];
long long sizes[500005]; // fiecare nod in ce componenta conexa este

void dfs (int x){
    if (comp[x] != 0)
        return;
    sizes[numComp]++;
    comp[x] = numComp;
    for (auto idx:graph[x])
        dfs(idx);
}

int main (){
    int x, y;
    char transport;

    cin >> nodes >> edges;
    for (int i=1; i<=edges; ++i){
        cin >> x >> y >> transport;

        if (transport == 'T'){
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        else if (transport == 'A'){
            numBuses++;
            buses[numBuses].first = x;
            buses[numBuses].second = y;
        }
    }

    numComp = 0;
    for (int i=1; i<=nodes; ++i){
        if (comp[i] == 0){
            numComp++; // nr componente conexte formate din muchii cu trenuri
            dfs(i);
        }
    }

    for (int i=1; i<=numBuses; ++i){
        int set1, set2;

        set1 = comp[buses[i].first];
        set2 = comp[buses[i].second];

        if (set1 != set2){
            graphBuses[set1].push_back(set2);
            graphBuses[set2].push_back(set1); // graful componentelor conexe
        }
    }

    long long current, bestcitites = -1, ans;
    for (int i=1; i<=numComp; ++i){ // consideram ca sta in unul dintre orasele din fiecare ctc pe rand
        current = sizes[i];
        frecv.insert(i); // poate sa fie busses care merg dintr-o componenta conexte in alta de mai multe ori
        for (auto idx:graphBuses[i]){ 
            if (frecv.find(idx) == frecv.end()){ // nu am mai fost pe aci din componenta asta conexa
                current += sizes[idx];
                frecv.insert(idx);
            }
        }
        if (current == bestcitites){
            ans += sizes[i];
        }
        else if (current > bestcitites){
            bestcitites = current;
            ans = sizes[i];
        }
        frecv.clear();
    }
    cout << ans;
    return 0;
}

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