Submission #198166

#	Time	Username	Problem	Language	Result	Execution time	Memory
198166		model_code	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	100 / 100	1806 ms	40224 KiB

menesinis_bilietas

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

struct vertex {
    int group;
    vector<int> train_edges;
    vector<int> bus_edges;
    bool visited;

    vertex(): group(-1), visited(false) {}
};
vector<vertex> map;

void paint_graph(int idx, int colour) {
    assert(map[idx].group == -1);

    vertex& v = map[idx];
    v.group = colour;

    for (const int& sidx : v.train_edges) {
        assert(0 <= sidx && sidx < map.size());

        vertex& sibling = map[sidx];

        if (sibling.group != -1)
            continue;

        paint_graph(sidx, colour);
    }
}

int find_adjacent_comps(int idx, vector<bool>& adjacent) {
    assert(!map[idx].visited);
    vertex& v = map[idx];
    v.visited = true;

    int size = 1;

    for (const int& sidx : v.bus_edges) {
        assert(0 <= sidx && sidx < map.size());

        vertex& sibling = map[sidx];
        adjacent[sibling.group] = true;
    }

    for (const int& sidx : v.train_edges) {
        assert(0 <= sidx && sidx < map.size());

        vertex& sibling = map[sidx];

        if (sibling.visited)
            continue;

        size += find_adjacent_comps(sidx, adjacent);
    }

    return size;
}

int find_full_comp_size(int idx, int groups) {
    vector<bool> bitset(groups, false);
    bitset[map[idx].group] = true; // Always visit yourself

    int size = find_adjacent_comps(idx, bitset);

    for (int i = 0; i < groups; i++)
        if (!bitset[i])
            return 0;

    return size;
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin >> n >> m;
    map.resize(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        char c;
        cin >> a >> b >> c;
        if (c == 'T') {
            map[a-1].train_edges.push_back(b-1);
            map[b-1].train_edges.push_back(a-1);
        } else {
            map[a-1].bus_edges.push_back(b-1);
            map[b-1].bus_edges.push_back(a-1);
        }
    }

    int group = 0;
    for (int i = 0; i < n; i++)
        if (map[i].group == -1)
            paint_graph(i, group++);

    int size = 0;
    for (int i = 0; i < n; i++)
        if (!map[i].visited)
            size += find_full_comp_size(i, group);

    cout << size << endl;

    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from menesinis_bilietas.cpp:4:
menesinis_bilietas.cpp: In function 'void paint_graph(int, int)':
menesinis_bilietas.cpp:25:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(0 <= sidx && sidx < map.size());
                             ~~~~~^~~~~~~~~~~~
menesinis_bilietas.cpp: In function 'int find_adjacent_comps(int, std::vector<bool>&)':
menesinis_bilietas.cpp:44:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(0 <= sidx && sidx < map.size());
                             ~~~~~^~~~~~~~~~~~
menesinis_bilietas.cpp:51:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(0 <= sidx && sidx < map.size());
                             ~~~~~^~~~~~~~~~~~

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