Submission #1235588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235588		jundi	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	195 ms	7956 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];
        ds.unionByRank(p[i].fi,p[i].se);
    }
    vector<int> cnt(n+1,0);
    for(int i=1;i<=n;i++){
        cnt[ds.findUPar(i)]++;
    }
    int ans=0;
    for(int i=0;i<n+1;i++){
        ans=max(ans,cnt[i]);
    }
    cout<<ans<<endl;
}

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