Submission #1139323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139323		teo_55	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	404 ms	69044 KiB

menesinis_bilietas

#include<iostream>
#include<vector>
#include<set>
#include<bitset>
//#include<cassert>
const int NMAX=500005;
struct bus_edge{
    int from, to;
};
std::vector<int>t(NMAX), cnt(NMAX, 1);
std::vector<bus_edge>rem;
std::bitset<NMAX>f;
std::set<int>S[NMAX];
int n, m, nr_cc, ans=0;
inline int root(int x)
{
    if(!t[x])
        return x;
    t[x]=root(t[x]);
    return t[x];
}
inline void unite(int x, int y)
{
    int rx=root(x), ry=root(y);
    if(rx==ry)
        return;
    --nr_cc;
    if(cnt[rx]>cnt[ry])
    {
        cnt[rx]+=cnt[ry];
        t[ry]=rx;
        return;
    }
    cnt[ry]+=cnt[rx];
    t[rx]=ry;
}
void read()
{
    std::cin>>n>>m;
    nr_cc=n;
    for(int i=0; i<m; ++i)
    {
        int from, to;
        char type;
        std::cin>>from>>to>>type;
        if(type=='T')
            unite(from, to);
        else if(type=='A')
            rem.push_back({from, to});
    }
}
void solve()
{
    for(auto it:rem)
    {
        int rFrom=root(it.from);
        int rTo=root(it.to);
        if(rFrom!=rTo)
        {
            S[rFrom].insert(rTo);
            S[rTo].insert(rFrom);
        }
    }
    for(int i=1; i<=n; ++i)
    {
        int r=root(i);
        if(!f[r])
        {
            if(S[r].size()==nr_cc-1)
                ans+=cnt[r];
            f[r]=true;
        }
    }
    std::cout<<ans;
}
int main()
{
    std::ios_base::sync_with_stdio(false);
    read();
    solve();
    return 0;
}

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