Submission #335559

#	Time	Username	Problem	Language	Result	Execution time	Memory
335559		aanastasov	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	290 ms	22252 KiB

supertrees

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

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);
                }
        }
        // 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 groupIndex = std::vector<int>(nodes, -1);
        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();
                groupIndex[src] = disjointSets.size();
                group.push_back(src);
                for (int dst : component) if (!visited[dst] && p[src][dst] == 1) {
                    visited[dst] = true;
                    order.push(dst);
                }
            }

            for (int src : group) {
                for (int dst : group)
                    if (src != dst && p[src][dst] != 1) return 0;
                for (int dst : component) 
                    if (src != dst && groupIndex[dst] != disjointSets.size() && p[src][dst] != 2) return 0;
            }
            disjointSets.push_back(group);
        }
        if (disjointSets.size() == 2) return 0;
        // Step 4: Connect the resulting 1-tree.
        for (int index = 0; index < disjointSets.size(); ++index) {
            int curRepr = disjointSets[index][0];
            int nextRepr = disjointSets[(index + 1) % disjointSets.size()][0];
            if (disjointSets.size() > 1)
                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:59:55: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                     if (src != dst && groupIndex[dst] != disjointSets.size() && p[src][dst] != 2) return 0;
supertrees.cpp:65:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int index = 0; index < disjointSets.size(); ++index) {
      |                             ~~~~~~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:70:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for (int j = 1; j < disjointSets[index].size(); ++j) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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