Submission #1140183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140183		argon1	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	Compilation error	0 ms	0 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], 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;
}

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'void unite(int, int)':
menesinis_bilietas.cpp:26:13: error: reference to 'size' is ambiguous
   26 |         if (size[x] < size[y]) swap(x, y);
      |             ^~~~
In file included from /usr/include/c++/11/string:54,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from menesinis_bilietas.cpp:1:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
menesinis_bilietas.cpp:12:23: note:                 'int size [500001]'
   12 | int parent[MAXN + 1], size[MAXN + 1];
      |                       ^~~~
menesinis_bilietas.cpp:26:23: error: reference to 'size' is ambiguous
   26 |         if (size[x] < size[y]) swap(x, y);
      |                       ^~~~
In file included from /usr/include/c++/11/string:54,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from menesinis_bilietas.cpp:1:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
menesinis_bilietas.cpp:12:23: note:                 'int size [500001]'
   12 | int parent[MAXN + 1], size[MAXN + 1];
      |                       ^~~~
menesinis_bilietas.cpp:28:9: error: reference to 'size' is ambiguous
   28 |         size[x] += size[y];
      |         ^~~~
In file included from /usr/include/c++/11/string:54,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from menesinis_bilietas.cpp:1:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
menesinis_bilietas.cpp:12:23: note:                 'int size [500001]'
   12 | int parent[MAXN + 1], size[MAXN + 1];
      |                       ^~~~
menesinis_bilietas.cpp:28:20: error: reference to 'size' is ambiguous
   28 |         size[x] += size[y];
      |                    ^~~~
In file included from /usr/include/c++/11/string:54,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from menesinis_bilietas.cpp:1:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
menesinis_bilietas.cpp:12:23: note:                 'int size [500001]'
   12 | int parent[MAXN + 1], size[MAXN + 1];
      |                       ^~~~
menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:42:9: error: reference to 'size' is ambiguous
   42 |         size[i] = 1;
      |         ^~~~
In file included from /usr/include/c++/11/string:54,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from menesinis_bilietas.cpp:1:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
menesinis_bilietas.cpp:12:23: note:                 'int size [500001]'
   12 | int parent[MAXN + 1], size[MAXN + 1];
      |                       ^~~~