Submission #1140173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140173		andreifilimon	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	450 ms	125556 KiB

menesinis_bilietas

#include <bits/stdc++.h>
using namespace std;

struct DSU
{
    vector<int> tata, rsz;

    DSU(int n) : tata(n), rsz(n, 0)
    {
        for (int i = 0; i < n; i++)
            tata[i] = i;
    }

    int find_set(int v)
    {
        if (tata[v] == v) return v;
        tata[v] = find_set(tata[v]);
        return tata[v];
    }

    void union_set(int a, int b)
    {
        a = find_set(a);
        b = find_set(b);
        if (a != b)
        {
            if (rsz[a] < rsz[b]) tata[a] = b;
            else if (rsz[a] > rsz[b]) tata[b] = a;
            else tata[b] = a, rsz[a]++;
        }
    }
};

int main()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> tedge;
    vector<pair<int,int>> bedge;
    for(int i = 0; i < m; i++)
    {
        int a, b;
        char ch;
        cin >> a >> b >> ch;
        a--;
        b--;
        if(ch == 'T') tedge.push_back({a, b});
        else bedge.push_back({a, b});
    }

    DSU dsu(n);
    for(auto &e : tedge)
        dsu.union_set(e.first, e.second);

    unordered_map<int,int> dtoid;
    vector<int> compid(n);
    int nextid = 0;
    for(int i = 0; i < n; i++)
    {
        int r = dsu.find_set(i);
        if(!dtoid.count(r))
            dtoid[r] = nextid++;
        compid[i] = dtoid[r];
    }

    int k = nextid;
    if(k == 1)
    {
        cout << n << "\n";
        return 0;
    }

    vector< unordered_set<int> > adj(k);
    for(auto &e : bedge)
    {
        int c1 = compid[e.first];
        int c2 = compid[e.second];
        if(c1 != c2)
        {
            adj[c1].insert(c2);
            adj[c2].insert(c1);
        }
    }

    vector<int> compsz(k, 0);
    for(int i = 0; i < n; i++)
        compsz[compid[i]]++;

    long long ans = 0;
    for(int i = 0; i < k; i++)
        if((int)adj[i].size() == k - 1)
            ans += compsz[i];

    cout << ans;
    return 0;
}

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