Submission #1096578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096578		andrewp	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	100 / 100	844 ms	113684 KiB

menesinis_bilietas

//Dedicated to my love, ivaziva
#pragma GCC optimize("Ofast") 
#include <bits/stdc++.h> 
using namespace std;   
 
#define int long long 
 
using pii = pair<int, int>;
using ll = int64_t;  
  
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back  
#define dbg(x) cerr<<#x<<": "<<x<<'\n';  
#define dbga(A,l_,r_){for(int i_=l_;i_<=r_;i_++)cerr<<A[i_]<<' ';cerr<<'\n';}
#define dbgv(a_){for(auto x_:a_) cerr<<x_<<' ';cerr<<'\n';}   

const int maxn = 5e5 + 20;
int n, m, par[maxn], sz[maxn], comp[maxn], fa[maxn]; 
vector<int> g[2 * maxn];
bool was[maxn];

int get(int x) {
    return x == par[x] ? x : par[x] = get(par[x]);
}

void join(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) {
        return;
    }
    if (sz[a] < sz[b]) {
        swap(a, b);
    } 
    par[b] = a; 
    sz[a] += sz[b]; 
}

int32_t main()  {
    ios::sync_with_stdio(false); cin.tie(nullptr);  
    cout.tie(nullptr); cerr.tie(nullptr);
   
    cin >> n >> m;
    vector<pii> a, t;
    for (int i = 0; i < m; i++) {
        int u, v;
        char c;
        cin >> u >> v >> c;
        if (c == 'A') {
            a.pb({u, v});
        } else {
            t.pb({u, v});
        } 
    }
    for (int i = 1; i <= n; i++) {
        par[i] = i, sz[i] = 1; 
        was[i] = false, comp[i] = 0; 
    }
    for (auto x : t) { 
        int u = x.first, v = x.second;
        join(u, v);
    }
    int c = n + 1, br = 0; 
    for (int i = 1; i <= n; i++) { 
        int x = get(i); 
        if (!was[x]) {
            comp[i] = c;
            fa[c] = x; 
            comp[x] = c++;
            br++;  
            was[x] = true; 
        } else {
            comp[i] = comp[x]; 
        }
    }     
    map<pii, bool> alr;
    for (auto x : a) {
        int u = x.first, v = x.second;
        u = comp[u], v = comp[v];
        if (u == v || alr[{u, v}]) {
            continue; 
        } 
        g[u].pb(v);
        g[v].pb(u); 
        alr[{u, v}] = true, alr[{v, u}] = true;
    }
    int ans = 0;
    dbg(br);
    for (int i = n + 1; i <= n + br; i++) {
        if ((int)(g[i].size()) == br - 1) {
            ans += sz[get(fa[i])];
        }
    }
    cout << ans << '\n';
    return 0;   
}

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