Submission #1139313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139313		teo_55	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	10 / 100	92 ms	27776 KiB

menesinis_bilietas

#include<iostream>
#include<vector>
#include<set>
#include<bitset>
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[x]>cnt[y])
    {
        cnt[x]+=cnt[y];
        t[ry]=rx;
        return;
    }
    cnt[y]+=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()
{
    if(nr_cc==1)
        std::cout<<n;
    else
        std::cout<<0;
    return;
}
int main()
{
    std::ios_base::sync_with_stdio(false);
    read();
    solve();
    return 0;
}

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