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>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define int long long
vector<int> pa, rk;
int getParent(int n) {
if (pa[n] == n) return n;
return pa[n] = getParent(pa[n]);
}
void mge(int x, int y) {
if (x == y) return;
if (rk[x] > rk[y]) {
pa[y] = x;
} else if (rk[x] == rk[y]) {
pa[y] = x;
rk[x]++;
} else {
pa[x] = y;
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M, A, B, x, y;
char T;
cin >> N >> M;
pa.resize(N);
rk.resize(N);
for (int i = 0; i < N; i++) pa[i] = i;
fill(rk.begin(), rk.end(), 0);
unordered_map<int, unordered_set<int>> busadj;
vector<pair<int, int>> bus;
vector<int> ch[N];
while (M--) {
cin >> A >> B >> T;
A--; B--;
if (T == 'T') {
mge(getParent(A), getParent(B));
} else {
bus.push_back(make_pair(A, B));
}
}
for (int i = 0; i < N; i++) {
ch[getParent(i)].push_back(i);
}
for (pair<int, int> route: bus) {
x = getParent(route.first);
y = getParent(route.second);
if (x == y) continue;
busadj[x].insert(y);
busadj[y].insert(x);
}
int C = 0;
for (pair<int, unordered_set<int>> station: busadj) {
if (station.second.size() + 1 == busadj.size()) {
C += ch[station.first].size();
}
}
cout << C;
return 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... |