Submission #304900

#	Time	Username	Problem	Language	Result	Execution time	Memory
304900		computerbox	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	100 / 100	704 ms	80924 KiB

menesinis_bilietas

#include <bits/stdc++.h>
#define FLASH ios_base::sync_with_stdio(0);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";


using namespace std;


ll n,m;
struct edge
{
  ll x,y;	
};



vector<edge>bus;
set<ll>adj[500010];

ll par[500010];
ll rankk[500010];

void make_set(ll n)
{
  for(ll i=0;i<=n;i++){rankk[i]=1;par[i]=i;}	
}

ll findd(ll v)
{
 while(par[v]!=v)
 {
  par[v]=par[par[v]];
  v=par[v];
 }	
 return v;
}


void make_union(ll a,ll b)
{
  a=findd(a);b=findd(b);
  if(a!=b)
  {
	if(rankk[a]>rankk[b])swap(a,b);
	rankk[b]+=rankk[a];
	par[a]=par[b];  
  }	
}


int main(){
FLASH;
cin>>n>>m;
make_set(n);
for(ll i=1;i<=m;i++)
{
 ll x,y;
 char z;
 cin>>x>>y>>z;
 if(z=='T')
 {
  make_union(x,y); 
 }
 else bus.pb({x,y});	
	
}

for(auto i:bus)
{
  if(findd(i.x)!=findd(i.y))
  {
    adj[findd(i.x)].insert(findd(i.y));
    adj[findd(i.y)].insert(findd(i.x));
  }	
}
ll cnt=0;
for(ll i=1;i<=n;i++)
{
  ll p=findd(i);
  if(p==i)
  {
    cnt++;
  }	
}


ll ans=0;
for(ll i=1;i<=n;i++)
{
  ll p=findd(i);
  if(p==i)
  {
	ll sz=(ll)adj[i].size();
	if(sz==cnt-1)ans+=rankk[i];  
  }	
}

cout<<ans<<endl;
return 0;
} 

• Subtask 1: 10 / 10
• Subtask 2: 6 / 6
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35
• Subtask 5: 19 / 19