Submission #1235691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235691		jundi	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	576 ms	49920 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,m;
    cin>>n>>m;
    DisjointSet ds(n);
    vector<pair<int, int>> p(m);
    vector<char> t(m);
    for (int i=0;i<m;i++){
        cin>>p[i].fi>>p[i].se>>t[i];
        p[i].fi--; p[i].se--;
        if(t[i]=='T') ds.unionByRank(p[i].fi,p[i].se);
    }

    vector<int> reindex(n,-1); //T组合数
    map<int,int> remap;
    int cnt=0;
    for (int i=0;i<n;i++) {
        int r=ds.findUPar(i);
        if (remap.find(r)==remap.end()){ 
            remap[r]=cnt;
            cnt++;
        }
        reindex[i]=remap[r];
    }
    // for(int i=0;i<n;i++){
    //     cout<<reindex[i]<<" "<<remap[i]<<" "<<remap[ds.findUPar(i)]<<endl;
    // }

    vector<int> resize(cnt, 0); //T组合大小
    for (int i=0;i<n;i++) {
        resize[reindex[i]]++;
    }
    // for(int i=0;i<cnt;i++){
    //     cout<<resize[i]<<" ";
    // }

    set<pair<int,int>> connect; //不同T组合之间用A连接的方法
    for (int i=0;i<m;i++) {
        if (t[i]!='A') continue;
        int a=reindex[p[i].fi];
        int b=reindex[p[i].se];
        if (a==b) continue; //已经在一组
        if (a>b) swap(a,b);
        // cout<<a<<" "<<b<<endl;
        connect.insert({a,b});
    }

    vector<int> d(cnt,0); //从其他组合到这个组合的方法数
    for (auto i:connect) {
        d[i.fi]++; d[i.se]++;
    }
    // cout<<endl;
    // for(int i=0;i<cnt;i++){
    //     cout<<i<<" "<<d[i]<<endl;
    // }

    long long ans=0;
    for (int i=0;i<cnt;i++) {
        if (d[i]==cnt-1) {
            ans+=resize[i];
        }
    }
    cout<<ans;
}

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