This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
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());
| ~~~~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |