Submission #1215311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215311		juanmartinez111	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	740 ms	120968 KiB

menesinis_bilietas

#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(), a.rend()
#define forn(u,n) for(int u=0;u<n;++u)
#define forns(u,i,n) for(int u=i;u<n;++u)
#define todo0(a) memset(a,0,sizeof a)
#define todom1(a) memset(a,-1,sizeof a)
#define reverso int, vector<int>, greater<int>
#define sz(a) ((int)a.size())
#define pb push_back
#define snd second
#define fst first

using namespace std;

typedef long long ll;

const long long  MOD = 1000567999;
const int N = 500001;

int parent[N];
int rank_dsu[N];

// Finds representative of DSU
int find_parent(int v) {
  return parent[v] = (v == parent[v] ? v : find_parent(parent[v]));
}

void make_set(int v){
  parent[v] = v;
  rank_dsu[v] = 1;
}

void join(int u, int  v){
  u = find_parent(u);
  v = find_parent(v);
  if (u != v){
    // Add tree of lower rank_dsued node to the higher one
    if (rank_dsu[v] > rank_dsu[u])
      swap(u, v);

    parent[v] = u;
    rank_dsu[u]+=rank_dsu[v];
  }
}
int main(){
    #ifdef LOCAL
    freopen("entra.in","r",stdin);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>>buses;
    forns(i,1,n+1){
        make_set(i);
    }
    forn(i,m){
        int u,v;
        string s;
        cin>>u>>v>>s;
        if(s=="T"){
            join(u,v);
        }
        else{
            buses.pb({u,v});
        }
    }
    set<int>sets;
    for(int i=1;i<=n;i++)sets.insert(find_parent(i));
    int cnt=(int)sets.size();
    ll ans=0;
    map<int,set<int>>groups;
    for(auto [u,v]:buses){
        u=find_parent(u);
        v=find_parent(v);
        if(u==v)continue;
        groups[u].insert(v);
        groups[v].insert(u);
    }
    set<int>taken;
    forns(i,1,n+1){
        int u=find_parent(i);
        if(taken.count(u))continue;
        if(1+(int)groups[u].size()==cnt)ans+=rank_dsu[u];
        taken.insert(u);
    }
    cout<<ans<<endl;
}

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