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;
#define F first
#define S second
#define mp make_pair
#define pb push_back
const int N = 5000005;
int p[N];
int sz[N];
set<int> reps;
set<pair<int, int>, less<pair<int, int>>> adj[N];
void make(int v){p[v]=v; sz[v]=1;}
int rep(int v){
if(p[v]==v)return v;
return p[v]=rep(p[v]);
}
void unite(int v, int u){
v=rep(v);
u=rep(u);
if(u==v)return;
if(sz[u]>sz[v]){
swap(u, v);
}
p[v]=u;
sz[u]+=sz[v];
reps.erase(reps.find(v));
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<pair<int, int>> free;
vector<pair<int, int>> paid;
for(int i=1; i<=n; i++){
make(i);
reps.insert(i);
}
for(int i=0; i< m; i++){
int x, y;
char a;
cin >> x >> y >> a;
if(a=='T'){
free.pb(mp(x, y));
}
else paid.pb(mp(x, y));
}
for(int i=0; i<free.size(); i++){
unite(free[i].F, free[i].S);
}
for(int i=0; i< paid.size(); i++){
int x=paid[i].F;
int y=paid[i].S;
x=rep(x);
y=rep(y);
adj[x].insert(mp(x, y));
adj[y].insert(mp(x, y));
adj[y].insert(mp(y, x));
adj[x].insert(mp(y, x));
}
int ans=0;
for(auto it = reps.begin(); it!=reps.end(); it++){
int node=*it;
if(adj[node].size()==2*(reps.size()-1)){
ans+=sz[node];
}
}
cout << ans << '\n';
}
Compilation message (stderr)
menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i=0; i<free.size(); i++){
| ~^~~~~~~~~~~~
menesinis_bilietas.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=0; i< paid.size(); i++){
| ~^~~~~~~~~~~~~
# | 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... |