Submission #235225

#	Time	Username	Problem	Language	Result	Execution time	Memory
235225		rama_pang	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	100 / 100	207 ms	29668 KiB

menesinis_bilietas

#include <bits/stdc++.h>
using namespace std;
using lint = long long;

const int MAXN = 500005;

int N, M;
vector<int> adj[MAXN];

int p[MAXN];
int Find(int x) {
  return p[x] == x ? x : p[x] = Find(p[x]);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> M;
  iota(p, p + MAXN, 0);

  vector<pair<int, int>> edge;
  for (int i = 0; i < M; i++) {
    int u, v;
    string s;
    cin >> u >> v >> s;
    if (s == "T") {
      p[Find(u)] = Find(v);
    } else {
      edge.emplace_back(u, v);
    }
  }

  int cc = 0;
  for (int i = 1; i <= N; i++) {
    if (Find(i) == i) {
      cc++;
    }
  }

  vector<pair<int, int>> se;
  for (auto e : edge) {
    int u = e.first;
    int v = e.second;
    u = Find(u);
    v = Find(v);
    if (u == v) continue;
    se.emplace_back(min(u, v), max(u, v));
  }
  sort(begin(se), end(se));
  se.resize(unique(begin(se), end(se)) - begin(se));

  vector<int> deg(N + 1);
  for (auto i : se) {
    deg[i.first]++;
    deg[i.second]++;
  }

  int ans = 0;
  for (int i = 1; i <= N; i++) {
    if (deg[Find(i)] == cc - 1) {
      ans++;
    }
  }

  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