Submission #1235642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235642		hq77	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	200 ms	3912 KiB

menesinis_bilietas

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

#include <bits/stdc++.h>
using namespace std;
vector<int>Size,parent;
vector<int>rrank;

int get(int x){
    int root=parent[x];
    if(parent[root]==root)return root;
    return parent[x]=get(parent[x]);
}

void merge(int x,int y){
    int rootx=get(x);
    int rooty=get(y);
    // cout<<x<<" "<<y<<endl;
    if(rootx==rooty)return;
    if(rrank[rootx]<rrank[rooty]){
        parent[rootx]=rooty;
    }
    else if(rrank[rooty]<rrank[rootx]){
        parent[rooty]=rootx;
    }
    else{
        parent[rooty]=rootx;
        rrank[rootx]++;
    }
    // cout<<x<<" "<<parent[x]<<" "<<y<<" "<<parent[y]<<endl;
}


int main() {
	int n,m;cin>>n>>m;
    parent.resize(n);
    // Size.resize(n+1,1);
    rrank.resize(n+1,0);
    for(int i=0;i<n;i++){
        parent[i]=i;
    }
    for(int i=0;i<m;i++){
        int a,b;char t;cin>>a>>b>>t;
        if(t=='T'){
            merge(a-1,b-1);
        }
    }

    // for(int i=0;i<n;i++)cout<<parent[i]<<" ";
    // cout<<endl;

    sort(parent.begin(),parent.end());
    int cnt=0,maxx=0;
    for(int i=0;i<n;i++){
        if(i==0){cnt++;continue;}
        if(parent[i]!=parent[i-1]){
            maxx=max(maxx,cnt);
            cnt=0;
        }
        // cout<<cnt<<" "<<maxx<<endl;
        cnt++;
    }
    maxx=max(maxx,cnt);
    if(maxx==n)cout<<0;
    else cout<<n;
    
}

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