Submission #1235668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235668		hq77	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	10 / 100	188 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]);
// }

int get(int x) {
    if (parent[x] != x) {
        parent[x] = get(parent[x]);
    }
    return 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);
    // cout<<maxx;
    // if(count(parent.begin(),parent.end(),parent[0])!=n)cout<<0;
    // else cout<<n;

    int first_component = get(0);
    bool all_connected = true;
    
    for (int i = 1; i < n; i++) {
        if (get(i) != first_component) {
            all_connected = false;
            break;
        }
    }
    
    if (all_connected) {
        cout << n << endl;  // All cities are valid starting points
    } else {
        cout << 0 << endl;  // No city can reach all others
    }
    
}

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