제출 #1141414

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141414		ionutza	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	415 ms	40256 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], sizes[500005]; // fiecare nod in ce componenta conexa este

void dfs (int x){
    if (comp[x])
        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{
            numBuses++;
            buses[numBuses].first = x;
            buses[numBuses].second = y;
        }
    }

    for (int i=1; i<=nodes; ++i){
        if (comp[i] == 0){
            numComp++;
            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);
        }
    }

    long long current, bestcitites, ans;
    for (int i=1; i<=numComp; ++i){
        current = sizes[i];
        frecv.insert(i);
        for (auto idx:graphBuses[i]){
            if (frecv.find(idx) == frecv.end()){
                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