제출 #1235630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235630		jundi	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	187 ms	7812 KiB

menesinis_bilietas

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

class DisjointSet{
    vector<int> rank,parent;
public:
    DisjointSet(int n){ 
        rank.resize(n+1,0);
        parent.resize(n+1);
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
    }
    int findUPar(int node){  
        if(node== parent[node]) return node;
        else return parent[node]=findUPar(parent[node]);
    }
    void unionByRank(int u,int v){
        int pu=findUPar(u);
        int pv=findUPar(v);
        if(pu==pv) return;
        if(rank[pu]<rank[pv]){
            parent[pu]=pv;
        }
        else if(rank[pu]>rank[pv]){
            parent[pv]=pu;
        }
        else{
            parent[pv]=pu;
            rank[pu]++;
        }
    }
};

int main() {
	int n,q;
    cin>>n>>q;
    DisjointSet ds(n);
    vector<pair<int,int>> p(q);
    vector<char> t(q);
    for(int i=0;i<q;i++){
        cin>>p[i].fi>>p[i].se>>t[i];
        p[i].fi--; p[i].se--;
        if(t[i]=='T') ds.unionByRank(p[i].fi,p[i].se);
    }
    vector<int> cnt(n+1,0);
    for(int i=0;i<n;i++){
        cnt[ds.findUPar(i)]++;
        // cout<<i<<" "<<ds.findUPar(i)<<endl;
    }
    int ans=0;
    for(int i=0;i<n;i++){
        // cout<<cnt[i]<<" ";
        ans=max(ans,cnt[i]);
    }
    // cout<<endl;
    cout<<ans<<endl;
}

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