Submission #1139640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139640		sashaaaa	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	391 ms	123448 KiB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;

vector<int> parent, sizee;

int getroot(int v)
{
    if (parent[v] == v) return v;
    return parent[v] = getroot(parent[v]);
}

void union_set(int a, int b)
{
    a = getroot(a);
    b = getroot(b);
    if (a != b)
    {
        if (sizee[a] < sizee[b]) swap(a, b);
        parent[b] = a;
        sizee[a] += sizee[b];
    }
}

int main()
{
    cin.tie(nullptr);
    ios_base :: sync_with_stdio(false);

    int N, M;
    cin >> N >> M;

    vector<pair<int,int>> cfr, stb;
    cfr.reserve(M);
    stb.reserve(M);

    for(int i = 1; i <= M; i ++)
    {
        int a, b;
        char t;
        cin >> a >> b >> t;
        if(t == 'T')
        {
            cfr.push_back({a, b});
        }
        else
        {
            stb.push_back({a, b});
        }
    }

    parent.resize(N + 1);
    sizee.resize(N + 1, 1);

    for(int i = 1; i <= N; i++)
    {
        parent[i] = i;
    }

    for (auto & i : cfr)
    {
        union_set(i.first, i.second);
    }

    unordered_map<int,int> m;
    m.reserve(N);

    vector<int> which(N + 1, -1);
    int cnt = 0;

    for(int v = 1; v <= N; v ++)
    {
        int r = getroot(v);
        if(!m.count(r))
        {
            m[r] = cnt ++;
        }
        which[v] = m[r];
    }

    vector<int> marime(cnt, 0);
    for(int i = 1; i <= N; i ++)
    {
        marime[which[i]]++;
    }

    vector<unordered_set<int>> adj(cnt);
    for (auto & i : stb)
    {
        int x = which[i.first];
        int y = which[i.second];
        if (x != y)
        {
            adj[x].insert(y);
            adj[y].insert(x);
        }
    }

    int ans = 0;
    for(int i = 0; i < cnt; i ++)
    {
        if(adj[i].size() == cnt - 1)
        {
            ans += marime[i];
        }
    }

    cout << ans << '\n';

    return 0;
}

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