Submission #1235787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235787		hq77	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	65 / 100	3092 ms	65004 KiB

menesinis_bilietas

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

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>parent;
vector<vector<int>>adj;
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][0] != x) {
        parent[x][0] = get(parent[x][0]);
    }
    return parent[x][0];
}

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][0]=rooty;
        parent[rooty][1]++;
    }
    else if(rrank[rooty]<rrank[rootx]){
        parent[rooty][0]=rootx;
        parent[rootx][1]++;
    }
    else{
        parent[rooty][0]=rootx;
        rrank[rootx]++;
    }
    // cout<<x<<" "<<parent[x]<<" "<<y<<" "<<parent[y]<<endl;
}

bool unite(int x, int y){
    x=get(x); y=get(y);
    if(x==y)return 1;
    return 0;
}
vector<int>visited(1e6,0);
set<int>s;
void dfs(int node){
    visited[node]=1;
    // cout<<"node"<<node<<"  ";
    for(int i:adj[node]){
        // cout<<"visit"<<node<<" "<<i<<" "<<visited[i]<<" "<<endl;
        if(!visited[i]){
            // cout<<"node"<<node<<" "<<i<<"    "<<unite(i,node)<<endl<<endl;

            if(unite(i,node))dfs(i);
            else {//cout<<"insert"<<i<<" "<<get(i)<<endl;
                s.insert(get(i));
            }
        }
    }
    // cout<<"size"<<s.size()<<endl;
    // return s.size();
}
int main() {
	int n,m;cin>>n>>m;
    parent.resize(n,vector<int>(2));
    // Size.resize(n+1,1);
    rrank.resize(n+1,0);
    for(int i=0;i<n;i++){
        parent[i][0]=i;
        parent[i][1]=1;
    }
    adj.resize(n+1);
    for(int i=0;i<m;i++){
        int a,b;char t;cin>>a>>b>>t;
        if(t=='T'){
            merge(a-1,b-1);
            
        }
        // else{
            adj[a-1].push_back(b-1);
            adj[b-1].push_back(a-1);
        // }
    }
    map<int,int>mp;
    for(int i=0;i<n;i++){
        if(!mp[get(i)])mp[get(i)]=1;
        else mp[get(i)]++;
    }
    // cout<<mp.size();
    // if(mp.size()>3){cout<<0;return 0;}
    if(mp.size()==1){cout<<n;return 0;}
    int ans=0;
    for(auto i:mp){
        // cout<<i.first<<" "<<i.second<<endl;
        visited.clear();
        s.clear();
        for(int j=0;j<n;j++)visited[j]=0;
        // cout<<endl<<i.first<<endl;
        dfs(i.first);
        // cout<<i.first<<" "<<s.size()<<endl;
        if(s.size()==mp.size()-1){
            ans+=i.second;
        //     if(mp.size()==2){cout<<n<<endl;return 0;}
        //     else if(mp.size()==3){cout<<i.second;return 0;}
        }
    }
    cout<<ans;
    // 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 cnt=0;
    // for(int i=0;i<n;i++){
    //     if(rrank[i]==1)cnt++;
    // }
    // cout<<cnt;
    // 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: 0 / 10
• Subtask 2: 0 / 6
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35
• Subtask 5: 0 / 19