Submission #1140520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140520		12345678	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	16 / 100	335 ms	83096 KiB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

int n, m, sz[nx], g[nx], vs[nx], u, v, cnt, dp[nx], mx, res;
char t;
vector<int> d[nx];
vector<pair<int, int>> edg;
set<int> s[nx];

void dfs(int u, int hd)
{
    vs[u]=1;
    g[u]=hd;
    sz[hd]++;
    for (auto v:d[u]) if (!vs[v]) dfs(v, hd);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        cin>>u>>v>>t;
        if (t=='T') d[u].push_back(v), d[v].push_back(u);
        else edg.push_back({u, v});
    }
    for (int i=1; i<=n; i++) if (!vs[i]) dfs(i, ++cnt);
    for (auto [u, v]:edg) s[g[u]].insert(g[v]), s[g[v]].insert(g[u]);
    for (int i=1; i<=cnt; i++) 
    {
        dp[i]=sz[i];
        for (auto v:s[i]) dp[i]+=sz[v]; 
    }
    //for (int i=1; i<=n; i++) cout<<"g "<<i<<' '<<g[i]<<'\n';
    //for (int i=1; i<=cnt; i++) cout<<i<<' '<<sz[i]<<' '<<dp[i]<<'\n';
    for (int i=1; i<=cnt; i++) if (dp[i]==n) res+=sz[i];
    cout<<res;
}

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