oj.uz

Submission #498242

# Submission time Handle Problem Language Result Execution time Memory
498242 2021-12-24T16:28:42 Z aurims Monthly railway pass (LMIO18_menesinis_bilietas) C++14
100 / 100
 721 ms 40096 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

struct vertex {
    int group;               // kokiai jungumo komponenciu grupei priklauso
    vector<int> train_edges; // su kokiais miestais turi traukini
    vector<int> bus_edges;   // su kokiais miestais turi autika
    bool visited;            // ar aplankyta

    vertex(): group(-1), visited(false) {} // by default, neaplankyta ir nepriklauso jokiai jung. komp. grupei
};
vector<vertex> map;

// visas virsunes jungumo komponenteje priskiriam vienai grupei
void paint_graph(int idx, int colour) {
    assert(map[idx].group == -1);

    vertex& v = map[idx];
    v.group = colour; // priskiriam miesta prie grupes

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

        vertex& sibling = map[sidx];

        if (sibling.group != -1) // jei kaimynas turi grupe, tai skipinam ji
            continue;

        paint_graph(sidx, colour); // nuspalvinam kaimyna
    }
}

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); // jungumo komponenciu aplankymo sarasas
    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]) // jei yra neaplankyta jungumo komponente, tai vadinasi is miesto map[idx] neina aplankyt visu miestu pigiai
            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++) { // iteruojam per transporto linijas
        int a, b;
        char c;
        cin >> a >> b >> c;
        if (c == 'T') { // jei jungia traukinys
            // grafe sujungiam tas dvi virsunes
            map[a-1].train_edges.push_back(b-1);
            map[b-1].train_edges.push_back(a-1);
        } else { // jei jungia autikas
            // grafe sujungiam tas dvi virsunes
            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++) // iteruojam per miestus
        if (map[i].group == -1) // jeigu tas miestas dar nepriklauso jokiai grupei
            paint_graph(i, group++); // tai priskiriam ji kokiai grupei

    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

In file included from /usr/include/c++/10/cassert:44,
                 from menesinis_bilietas.cpp:4:
menesinis_bilietas.cpp: In function 'void paint_graph(int, int)':
menesinis_bilietas.cpp:26:34: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         assert(0 <= sidx && sidx < map.size());
      |                             ~~~~~^~~~~~~~~~~~
menesinis_bilietas.cpp: In function 'int find_adjacent_comps(int, std::vector<bool>&)':
menesinis_bilietas.cpp:45:34: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         assert(0 <= sidx && sidx < map.size());
      |                             ~~~~~^~~~~~~~~~~~
menesinis_bilietas.cpp:52:34: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         assert(0 <= sidx && sidx < map.size());
      |                             ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 36376 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 630 ms 29792 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 45 ms 3588 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 29792 KB Output is correct
2 Correct 2 ms 1100 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 472 KB Output is correct
6 Correct 100 ms 7068 KB Output is correct
7 Correct 721 ms 40096 KB Output is correct
8 Correct 7 ms 1740 KB Output is correct
9 Correct 11 ms 1772 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 472 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 3 ms 460 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 2 ms 472 KB Output is correct
21 Correct 2 ms 1100 KB Output is correct
22 Correct 7 ms 1740 KB Output is correct
23 Correct 11 ms 1772 KB Output is correct
24 Correct 45 ms 3588 KB Output is correct
25 Correct 7 ms 844 KB Output is correct
26 Correct 97 ms 6388 KB Output is correct
27 Correct 30 ms 2280 KB Output is correct
28 Correct 41 ms 2988 KB Output is correct
29 Correct 20 ms 1916 KB Output is correct
30 Correct 52 ms 3784 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 7 ms 844 KB Output is correct
17 Correct 97 ms 6388 KB Output is correct
18 Correct 30 ms 2280 KB Output is correct
19 Correct 41 ms 2988 KB Output is correct
20 Correct 20 ms 1916 KB Output is correct
21 Correct 52 ms 3784 KB Output is correct
22 Correct 422 ms 36376 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 630 ms 29792 KB Output is correct
26 Correct 0 ms 204 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 2 ms 472 KB Output is correct
29 Correct 2 ms 1100 KB Output is correct
30 Correct 100 ms 7068 KB Output is correct
31 Correct 721 ms 40096 KB Output is correct
32 Correct 7 ms 1740 KB Output is correct
33 Correct 11 ms 1772 KB Output is correct
34 Correct 45 ms 3588 KB Output is correct
35 Correct 25 ms 3584 KB Output is correct
36 Correct 256 ms 14436 KB Output is correct
37 Correct 194 ms 19616 KB Output is correct