# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
826036 | AlphaMale06 | Monthly railway pass (LMIO18_menesinis_bilietas) | C++14 | 451 ms | 74392 KiB |
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 = 500005;
int p[N];
int sz[N];
set<int> adj[N];
vector<pair<int, int>> paid;
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[u]=v;
sz[v]+=sz[u];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i=1; i<=n; i++){
make(i);
}
for(int i=0; i< m; i++){
int x, y;
char a;
cin >> x >> y >> a;
if(a=='T'){
unite(x, y);
}
else paid.pb(mp(x, y));
}
for(int i=0; i< paid.size(); i++){
int x=paid[i].F;
int y=paid[i].S;
x=rep(x);
y=rep(y);
if(x==y)continue;
adj[x].insert(y);
adj[y].insert(x);
}
int ans=0;
int cnt=0;
for(int i=1; i<=n; i++){
if(p[i]==i)cnt++;
}
for(int i=1; i<=n; i++){
if(p[i]==i){
if(adj[i].size()==cnt-1)ans+=sz[i];
}
}
cout << ans << '\n';
}
Compilation message (stderr)
# | 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... |