| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1140183 | argon1 | Monthly railway pass (LMIO18_menesinis_bilietas) | C++20 | 0 ms | 0 KiB |
#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], size[MAXN + 1];
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 (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
}
}
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;
size[i] = 1;
}
// 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;
}