Submission #1140205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140205		argon1	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	634 ms	102836 KiB

menesinis_bilietas

#include <bits/stdc++.h>
using namespace std;

#define MAX_CITIES 500001 // Maximum number of cities

vector<int> busGraph[MAX_CITIES];    // Adjacency list for bus connections
vector<int> trainGraph[MAX_CITIES];  // Adjacency list for train connections
set<int> componentNeighbors[MAX_CITIES]; // Neighboring components connected via a bus

int trainComponent[MAX_CITIES];      // Train component ID for each city
int componentSize[MAX_CITIES];       // Size of each train component

// Depth-First Search to assign train component IDs
void dfsTrain(int city, int componentID) {
    trainComponent[city] = componentID; // Assign current city to the current component
    ++componentSize[componentID];      // Increment the size of the current component

    // Visit all cities directly connected by train
    for (int neighbor : trainGraph[city]) {
        if (trainComponent[neighbor] == 0) { // If neighbor is unvisited
            dfsTrain(neighbor, componentID);
        }
    }
}

int main() {
    int numCities, numConnections; // Number of cities and connections
    cin >> numCities >> numConnections;

    // Read the graph
    for (int i = 0; i < numConnections; ++i) {
        int cityA, cityB;
        char connectionType;
        cin >> cityA >> cityB >> connectionType;
        --cityA, --cityB; // Convert to 0-based indexing
        if (connectionType == 'T') {
            // Train connection
            trainGraph[cityA].push_back(cityB);
            trainGraph[cityB].push_back(cityA);
        } else {
            // Bus connection
            busGraph[cityA].push_back(cityB);
            busGraph[cityB].push_back(cityA);
        }
    }

    // Step 1: Find train-connected components using DFS
    int componentCount = 1; // Component ID counter (1-based indexing)
    for (int i = 0; i < numCities; ++i) {
        if (trainComponent[i] == 0) { // If city is not yet assigned to a component
            dfsTrain(i, componentCount++);
        }
    }

    // Step 2: Find neighboring components connected by buses
    for (int city = 0; city < numCities; ++city) {
        for (int neighbor : busGraph[city]) {
            // If the bus connects two different train components
            if (trainComponent[city] != trainComponent[neighbor]) {
                int componentA = trainComponent[city];
                int componentB = trainComponent[neighbor];
                componentNeighbors[componentA].insert(componentB);
                componentNeighbors[componentB].insert(componentA);
            }
        }
    }

    // Step 3: Count valid components
    int result = 0; // Total number of valid cities
    for (int componentID = 1; componentID < componentCount; ++componentID) {
        // Check if the component can reach all other components except itself
        if (componentNeighbors[componentID].size() == componentCount - 2) {
            result += componentSize[componentID]; // Add the size of the valid component
        }
    }

    // Step 4: Output the result
    cout << result << '\n';

    return 0;
}

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