Submission #1179069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179069		prideliqueee	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	267 ms	38432 KiB

menesinis_bilietas

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define f first
#define s second
int p[500010];
int root(int u)
{
    if(p[u]==u)
    return u;
    return p[u]=root(p[u]);
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    int cnt=n;
    for(int i=1;i<=n;i++)
    p[i]=i;
    vector<pair<int,int>> w;
    for(int i=0;i<m;i++)
    {
        int u,v;
        char c;
        cin>>u>>v>>c;
        if(c=='A')
        {
            w.push_back({u,v});
        }
        else
        {
            if(root(u)==root(v))
            continue;
            cnt--;
            p[root(u)]=root(v);
        }
    }
    set<pair<int,int>> s;
    int sum[n+1];
    memset(sum,0,sizeof sum);
    for(auto x:w)
    {
        int u=x.f,v=x.s;
        u=root(u),v=root(v);
        if(u==v)
        continue;
        if(u>v)
        swap(u,v);
        if(s.count({u,v})==1)
        continue;
        sum[u]++;
        sum[v]++;
        s.insert({u,v});
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int u=root(i);
        if(sum[u]==cnt-1)
        ans++;
    }
    cout<<ans;
}

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