Submission #1186132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186132		nagorn_ph	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	423 ms	104340 KiB

menesinis_bilietas

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)

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

int n, m, par[N];
vector <pii> edge;

int dsu(int a){
    return par[a] = (a == par[a] ? a : dsu(par[a]));
}

int32_t main(){
    iShowSpeed;
    iota(par, par + N, 0ll);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; char c; cin >> u >> v >> c;
        if (c == 'T') {
            if (dsu(u) != dsu(v)) par[dsu(u)] = dsu(v);
        }
        else {
            edge.emb(u, v);
        }
    }
    unordered_map <int, int> mp, sz;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int a = dsu(i);
        if (mp.find(a) == mp.end()) mp[a] = ++cnt;
        sz[mp[a]]++;
    }
    set <int> bus[n + 1];
    for (auto [u, v] : edge) {
        int a = dsu(u), b = dsu(v);
        if (a != b) {
            // cout << u << " " << v << "\n";
            bus[mp[a]].emplace(mp[b]);
            bus[mp[b]].emplace(mp[a]);
        }
    }
    // for (int i = 1; i <= cnt; i++) {
    //     cout << i << ": ";
    //     cout << sz[i] << ": ";
    //     for (auto e : bus[i]) cout << e << " ";
    //     cout << "\n";
    // }
    int ans = 0;
    for (int i = 1; i <= cnt; i++) {
        if (bus[i].size() == cnt - 1) ans += sz[i];
    }
    cout << ans;
}

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