제출 #1147528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147528		VMaksimoski008	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	16 / 100	481 ms	63868 KiB

menesinis_bilietas

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e5 + 5;

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 });
    }

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

        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: 0 / 30
• Subtask 4: 0 / 35
• Subtask 5: 0 / 19