Submission #1235788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235788		hq77	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	65 / 100	3095 ms	68868 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) {
    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;
}
vector<int>dp(1e6,0);
bool unite(int x, int y){
    if(!dp[x])dp[x]=get(x);
    if(!dp[y])dp[y]=get(y);
    if(dp[x]==dp[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;
    
    
}

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