Submission #1235620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235620		veehj	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	100 / 100	540 ms	69996 KiB

menesinis_bilietas

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(ll i=(ll)(a); i<(ll)(b); i++)
#define rrep(i, a, b) for(ll i=(ll)(a); i>=(ll)(b); i--)
#define vl vector<ll>
#define vpll vector<pair<ll, ll>>
#define vvl vector<vector<ll>>
#define pll pair<ll, ll>
//Monthly railway pass
ll n, m; 
vl pa, sz;
vpll iniadj;
vector<set<ll>> adj;

ll findgrp(ll x){
  if(pa[x]==x || pa[x]==-1) return x;
  return pa[x]=findgrp(pa[x]);
}

void merge(ll a, ll b){
  a=findgrp(a);
  b=findgrp(b);
  if(a==b) return;
  if(sz[a]<sz[b]) swap(a, b);
  pa[b]=a;
  sz[a]+=sz[b];
}

void link(ll a, ll b){
  a=findgrp(a);
  b=findgrp(b);
  if(a==b) return;
  adj[a].insert(b);
  adj[b].insert(a);
}

void f() {
  cin >> n >> m;
  pa.assign(n, -1);
  sz.assign(n, 1);
  adj.assign(n, {});
  rep(i, 0, m){
    ll a, b; char c; cin >> a >> b >> c; a--; b--;
    if(c=='A') iniadj.pb({a, b});
    else merge(a, b);
  }
  for(auto& u : iniadj){
    ll a=u.fi, b=u.se;
    link(a, b);
  }
  ll ans=0;
  rep(i, 0, n){
    if(findgrp(i)!=i) continue;
    ll cnt=sz[i];
    for(auto& u : adj[i]) cnt+=sz[u];
    if(cnt==n) ans+=sz[i];
  }
  cout << ans;
}

int main() {
  int tc = 1;
  // cin >> tc;
  for (int i = 1; i <= tc; i++) {
    // cout << '#' << i << endl;
    f();
    cout << endl;
  }
}

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