Submission #1186119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186119		PakinDioxide	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	100 / 100	260 ms	68136 KiB

menesinis_bilietas

/*
    author  : PakinDioxide
    created : 16/04/2025 14:22
    task    : temp
*/
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 5e5+5;
int n, m, par[mxN], vis[mxN];
set <int> adj[mxN];
vector <pair <int, int>> t, b;

int fi(int x) {
    if (x == par[x]) return x;
    return par[x] = fi(par[x]);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; char w;
        cin >> u >> v >> w;
        if (w == 'A') b.emplace_back(u, v);
        else t.emplace_back(u, v);
    }
    iota(par, par+n+1, 0);
    for (auto &[u, v] : t) par[fi(u)] = fi(v);
    int cnt = 0;
    for (int i = 1; i <= n; i++) if (!vis[fi(i)]) cnt++, vis[fi(i)] = 1;
    for (auto &[u, v] : b) if (fi(u) != fi(v)) adj[fi(u)].emplace(fi(v)), adj[fi(v)].emplace(fi(u));
    int ans = 0;
    for (int i = 1; i <= n; i++) if (adj[fi(i)].size() == cnt-1) ans++;
    
    cout << ans << '\n';
}

/*
we can merge the connected component first?
*/

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