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<bits/stdc++.h>
using namespace std;
struct Group{
vector<int>miestai;
vector<int>connections;
void mergeGroup(Group g){
for(int m:g.miestai) miestai.push_back(m);
for(int c:g.connections)
if(find(connections.begin(), connections.end(), c)==connections.end())
connections.push_back(c);
}
bool hasCity(int city){
return (find(miestai.begin(), miestai.end(), city)!=miestai.end());
}
bool hasConnection(int conn){
return (find(connections.begin(), connections.end(), conn)!=connections.end());
}
};
int N,M;
int find_group_with_city(vector<Group> grupes, int cityId) {
int curr = 0;
for (int i = 0; i < grupes.size(); i++) {
if(grupes[i].hasCity(cityId))return i;
}
return -1;
}
void create_group(int cityId, vector<Group> & grupes) {
Group g;
g.miestai.push_back(cityId);
grupes.push_back(g);
}
void change_ref(int from, int to, vector<Group> & grupes){
for(Group g: grupes){
for(int c: g.connections){
if(c==from)c=to;
}
}
}
//N-miestu skaicius M-transporto linijos
void dumpGroups(vector<Group> grupes){
for (Group g : grupes) {
for (int m : g.miestai) {
cout<<m<<" ";
}
cout<<" ----> ";
for (int c : g.connections) {
cout<<c<<" ";
}
cout<<endl;
}
}
int main() {
cin >> N >> M;
vector<Group> grupes;
int a, b;
char T;
for (int i = 0; i < M; i++) {
cin >> a >> b >> T;
int aG = find_group_with_city(grupes, a);
int bG = find_group_with_city(grupes, b);
if (T == 'T') {
// traukinys
if (aG + bG == -2) {
create_group(a, grupes);
aG = grupes.size() - 1;
}
if (aG != -1 && bG == -1) {
grupes[aG].miestai.push_back(b);
} else if (aG == -1 && bG != -1) {
grupes[bG].miestai.push_back(a);
} else {
// abu yra
grupes[aG].mergeGroup(grupes[bG]);
change_ref(bG, aG, grupes);
grupes.erase(grupes.begin() + bG);
}
} else {
if (aG == -1) {
create_group(a, grupes);
aG = grupes.size() - 1;
}
if (bG == -1) {
create_group(b, grupes);
bG = grupes.size() - 1;
}
if (!grupes[aG].hasConnection(bG))
grupes[aG].connections.push_back(bG);
if (!grupes[bG].hasConnection(aG))
grupes[bG].connections.push_back(aG);
}
// rysiai[a-1][b-1]=T;
// rysiai[b-1][a-1]=T;
}
int m=0;
for (Group g : grupes) {
if(g.connections.size()==grupes.size()-1){
//turi visas grupes
m+=g.miestai.size();
}
}
cout<<m<<endl;
}
Compilation message (stderr)
menesinis_bilietas.cpp: In function 'int find_group_with_city(std::vector<Group>, int)':
menesinis_bilietas.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Group>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i = 0; i < grupes.size(); i++) {
| ~~^~~~~~~~~~~~~~~
menesinis_bilietas.cpp:31:7: warning: unused variable 'curr' [-Wunused-variable]
31 | int curr = 0;
| ^~~~
# | 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... |