제출 #1140185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140185		argon1	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	182 ms	132464 KiB

menesinis_bilietas

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

const int MAXN = 500000;

vector<int> trainGraph[MAXN + 1];
vector<int> busGraph[MAXN + 1];
int parent[MAXN + 1], componentSize[MAXN + 1]; // Renamed 'size' to 'componentSize'
unordered_map<int, vector<int>> componentCities; // Cities in each train component
unordered_map<int, unordered_set<int>> componentNeighbors; // Components reachable via one bus

// Union-Find functions
int find(int x) {
    if (x != parent[x]) parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (componentSize[x] < componentSize[y]) swap(x, y); // Use componentSize here
        parent[y] = x;
        componentSize[x] += componentSize[y]; // Use componentSize here
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    // Initialize Union-Find
    for (int i = 1; i <= N; ++i) {
        parent[i] = i;
        componentSize[i] = 1; // Initialize component sizes
    }

    // Build the graph and merge train-connected components
    for (int i = 0; i < M; ++i) {
        int a, b;
        char type;
        cin >> a >> b >> type;
        if (type == 'T') {
            unite(a, b); // Merge train components
        } else if (type == 'A') {
            busGraph[a].push_back(b);
            busGraph[b].push_back(a);
        }
    }

    // Group cities by their train components
    for (int i = 1; i <= N; ++i) {
        int root = find(i);
        componentCities[root].push_back(i);
    }

    // Precompute neighbors of each train component via one bus trip
    for (int city = 1; city <= N; ++city) {
        int currentComponent = find(city);
        for (int neighbor : busGraph[city]) {
            int neighborComponent = find(neighbor);
            if (currentComponent != neighborComponent) {
                componentNeighbors[currentComponent].insert(neighborComponent);
            }
        }
    }

    // Calculate the maximum reachable cities for each train component
    unordered_map<int, int> maxReachableCities; // Stores reach count per component
    int globalMaxReachable = 0, countMaxCities = 0;

    for (const auto& [component, cities] : componentCities) {
        unordered_set<int> reachableCities(cities.begin(), cities.end());

        // Add cities from neighboring components
        for (int neighborComponent : componentNeighbors[component]) {
            reachableCities.insert(componentCities[neighborComponent].begin(),
                                   componentCities[neighborComponent].end());
        }

        int reachableCount = reachableCities.size();
        maxReachableCities[component] = reachableCount;

        // Track global maximum and count
        if (reachableCount > globalMaxReachable) {
            globalMaxReachable = reachableCount;
            countMaxCities = cities.size();
        } else if (reachableCount == globalMaxReachable) {
            countMaxCities += cities.size();
        }
    }

    cout << countMaxCities << "\n";
    return 0;
}

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