Submission #1220545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220545		juanmartinez111	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	6 / 100	377 ms	65368 KiB

menesinis_bilietas

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
int parent[500001];
int siz[500001];
int n,m;
void create(int nn){
    for(int i=1;i<=nn;i++){
        parent[i]=i;
        siz[i]=1;
    }
}
int find_parent(int indx){
    if(parent[indx]==indx)return indx;
    return parent[indx]=find_parent(parent[indx]);
}
void join(int a,int b){
    //Si voy a unir a con b
    //encuentro representativo de a y b;
    a=find_parent(a);
    b=find_parent(b);   
    if(siz[a]<siz[b]){
        parent[a]=parent[b];
        siz[b]+=siz[a];
    }
    else{
        parent[b]=parent[a];
        siz[a]+=siz[b];
    }
}
int main(){
    vector<pair<int,int>>buses;
    cin>>n>>m;
    create(n);
    for(int i=0;i<m;i++){
        int u,v;
        char type;
        cin>>u>>v>>type;
        //buses;
        if(type=='A'){
            buses.push_back({u,v});
        }
        else{
            join(u,v);
        }
    }
    set<int>TodosLosConjuntos[n+1];
    long long ans=0;
    vector<int>Padres;
    for(int i=1;i<=n;i++){
        if(find_parent(i)==i)Padres.push_back(i);
    }
    for(auto [nodeA,nodeB]:buses){
        nodeA=find_parent(nodeA);
        nodeB=find_parent(nodeB);
        TodosLosConjuntos[nodeA].insert(nodeB);
        TodosLosConjuntos[nodeB].insert(nodeA);
    }
    for(int i=1;i<=n;i++){
        if(TodosLosConjuntos[i].size()+1==Padres.size())ans+=siz[i];
    }
    cout<<ans<<endl;
    
}

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