Submission #335553

#	Time	Username	Problem	Language	Result	Execution time	Memory
335553		aanastasov	Connecting Supertrees (IOI20_supertrees)	C++17	Compilation error	0 ms	0 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <queue>
#include <iostream>

template<typename T> void debug(std::vector<T> v) {
    std::cout << "{";
    for (int i = 0; i < v.size(); ++i) {
        if (i != 0) std::cout << ", ";
        std::cout << v[i];
    }
    std::cout << "}" << "\n";
}

int construct(std::vector<std::vector<int>> p) {
    const int nodes = p.size();
    auto hasEdge = std::vector<std::vector<int>>(nodes, std::vector<int>(nodes, 0));
    auto marked = std::vector<bool>(nodes, false);
    for (int start = 0; start < nodes; ++start) {
        if (marked[start]) continue;
        // Step 1: Find all the nodes in the connected component that contains <start>.
        auto component = std::vector<int>();
        auto q = std::queue<int>();
        marked[start] = true;
        q.push(start);
        marked[start] = true;
        while (!q.empty()) {
            int src = q.front();
            q.pop();
            component.push_back(src);
            for (int dst = 0; dst < nodes; ++dst)
                if (p[src][dst] > 0 && !marked[dst]) {
                    marked[dst] = true;
                    q.push(dst);
                }
        }
        //debug(component);
        // Step 2: Check that all nodes in the component are connected to each other,
        // and that all pairs of nodes are connected by either one or two simple paths.
        for (int src : component)
            for (int dst : component) {
                if (src != dst && p[src][dst] == 0) return 0;
                if (p[src][dst] >= 3) return 0;
            }
        // Step 3: Divide all nodes into disjoint sets by going over only edges s.t. p[src][dst] = 1.
        auto disjointSets = std::vector<std::vector<int>>();
        auto visited = std::vector<bool>(nodes, false);
        auto order = std::queue<int>();
        for (int node : component) if (!visited[node]) {
            visited[node] = true;
            order.push(node);
            auto group = std::vector<int>();
            while (!order.empty()) {
                int src = order.front();
                order.pop();
                group.push_back(src);
                for (int dst : component) if (!visited[dst] && p[src][dst] == 1) {
                    visited[dst] = true;
                    order.push(dst);
                }
            }
            //debug(group);

            for (int src : group) {
                for (int dst : group)
                    if (src != dst && p[src][dst] != 1) return 0;
                for (int dst : component) {
                    if (src == dst) continue;
                    if (std::find(group.begin(), group.end(), dst) == group.end())
                        if (p[src][dst] != 2) return 0;
                }
            }
            disjointSets.push_back(group);
        }
        if (disjointSets.size() == 2) return 0;
        if (disjointSets.size() == 1) continue;
        // Step 4: Connect.
        for (int index = 0; index < disjointSets.size(); ++index) {
            int curRepr = disjointSets[index][0];
            int nextRepr = disjointSets[(index + 1) % disjointSets.size()][0];
            hasEdge[curRepr][nextRepr] = hasEdge[nextRepr][curRepr] = 1;
            for (int j = 1; j < disjointSets[index].size(); ++j) {
                int child = disjointSets[index][j];
                hasEdge[curRepr][child] = hasEdge[child][curRepr] = 1;
            }
        }
    }
    build(hasEdge);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:69:66: error: no matching function for call to 'find(std::vector<int>::iterator, std::vector<int>::iterator, int&)'
   69 |                     if (std::find(group.begin(), group.end(), dst) == group.end())
      |                                                                  ^
In file included from /usr/include/c++/9/bits/locale_facets.h:48,
                 from /usr/include/c++/9/bits/basic_ios.h:37,
                 from /usr/include/c++/9/ios:44,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from supertrees.cpp:4:
/usr/include/c++/9/bits/streambuf_iterator.h:373:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(std::istreambuf_iterator<_CharT>, std::istreambuf_iterator<_CharT>, const _CharT2&)'
  373 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/9/bits/streambuf_iterator.h:373:5: note:   template argument deduction/substitution failed:
supertrees.cpp:69:66: note:   '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' is not derived from 'std::istreambuf_iterator<_CharT>'
   69 |                     if (std::find(group.begin(), group.end(), dst) == group.end())
      |                                                                  ^
supertrees.cpp:78:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for (int index = 0; index < disjointSets.size(); ++index) {
      |                             ~~~~~~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:82:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             for (int j = 1; j < disjointSets[index].size(); ++j) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~