Submission #921046

#TimeUsernameProblemLanguageResultExecution timeMemory
921046zhehanMonthly railway pass (LMIO18_menesinis_bilietas)C++14
16 / 100
1628 ms194756 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int parent[500000]; int f(int a){ if(parent[a]==a){ return a; } return parent[a]=f(parent[a]); } void u(int a,int b){ parent[f(a)]=f(b); } signed main() { int n,m; cin>>n>>m; for(int i{1};i<n+1;++i){ parent[i]=i; } map<int,vector<int>> ma; for(int i{};i<m;++i){ int a,b; char c; cin>>a>>b>>c; if(c=='T'){ u(a,b); }else{ ma[a].push_back(b); ma[b].push_back(a); } } map<int,set<int>> mf; map<int,int> cc; for(int i{1};i<n+1;++i){ cc[f(i)]++; mf[f(i)].insert(-1); for(auto e:ma[i]){ mf[f(i)].insert(f(e)); } } int counter=0; for(auto e:mf){ if(mf.size()==e.second.size()){ counter+=cc[e.first]; } } cout<<counter; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...