Submission #1235608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235608		veehj	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	10 / 100	192 ms	33352 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;
struct id{
  ll leader, sz;
};
vector<id> grp;
vpll iniadj;
vector<set<ll>> adj;

ll findgrp(ll x){
  if(pa[x]==x) 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(grp[a].sz<grp[b].sz) swap(a, b);
  pa[b]=a;
  grp[a].sz+=grp[b].sz;
}

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

vector<bool> vist;
ll cities=0;
void connected(ll x){
  vist[x]=1;
  cities+=grp[x].sz;
  for(auto& u : adj[x]){
    if(vist[u]) continue;
    connected(u);
  }
}

void f() {
  cin >> n >> m;
  pa.assign(n, -1);
  grp.assign(n, {-1, 1});
  rep(i, 0, n){
    pa[i]=i;
    grp[i].leader=i;
  }
  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);
  }
  adj.assign(n, {});
  for(auto& u : iniadj){
    ll a=u.fi, b=u.se;
    link(a, b);
  }
  vist.assign(n, 0);
  cities=0;
  connected(findgrp(0));
  if(cities!=n){
    cout << 0;
    return;
  }
  set<ll> leaders, okleaders;
  rep(i, 0, n){
    ll x=findgrp(i);
    if(x!=i) continue;
    if(adj[i].size()!=1) okleaders.insert(i);
    leaders.insert(i);
  }
  if(leaders.size()==1 || leaders.size()==2){
    cout << n; return;
  }
  if(okleaders.size()!=1){
    cout << 0;
  } else {
    for(auto& u : okleaders) cout << grp[u].sz;
  }
}

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