Submission #1147536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147536		VMaksimoski008	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	571 ms	63876 KiB

menesinis_bilietas

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

struct union_find {
    int n;
    vector<int> par, size;
    union_find(int _n) : n(_n), par(n+1), size(n+1, 1) {
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int find(int u) {
        if(u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    void uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return ;
        if(size[a] < size[b]) swap(a, b);
        size[a] += size[b];
        par[b] = a;
    }

    int get_size(int u) {
        return size[find(u)];
    }
};

signed main() {
    int n, m; cin >> n >> m;
    union_find dsu(n);
    vector<ar<int, 2> > E;

    for(int i=1; i<=m; i++) {
        int a, b; char t;
        cin >> a >> b >> t;
        if(t == 'T') dsu.uni(a, b);
        else E.push_back({ a, b });
    }

    vector< set<int> > G(n+1);
    for(auto [a, b] : E) {
        a = dsu.find(a);
        b = dsu.find(b);
        if(a == b) continue;
        G[a].insert(b);
        G[b].insert(a);
    }

    int ans = 0;
    for(int i=1; i<=n; i++) {
        if(i != dsu.find(i)) continue;
        int cnt = dsu.get_size(i);
        for(int j : G[i]) cnt += dsu.get_size(j);
        if(cnt == n) ans += dsu.get_size(i);
    }
    cout << ans << '\n';
}

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