Submission #1237010

#TimeUsernameProblemLanguageResultExecution timeMemory
1237010i_love_mritiMonthly railway pass (LMIO18_menesinis_bilietas)C++20
10 / 100
187 ms3912 KiB
#include <bits/stdc++.h> using namespace std; const int mxN = 5e5 + 100; int par[mxN], sz[mxN], deg[mxN]; set<pair<int, int>> bus; int find(int u){ return u == par[u] ? u : par[u] = find(par[u]); } void unite(int u, int v){ u = find(u), v = find(v); if(u == v) return; par[u] = v, sz[v] += sz[u]; } int main(){ int n, m, u, v, ans = 0; cin >> n >> m; char ch; for(int i = 1; i <= n; ++i) sz[i] = 1, par[i] = i; for(int i = 0; i < m; ++i){ cin >> u >> v >> ch; if(u > v) swap(u, v); if(ch == 'T') unite(u, v); else bus.insert({u, v}); } int nn = 0; for(int i = 1; i <= n; ++i) nn += par[i] == i; if(sz[find(1)] == n){ cout << n << "\n"; return 0; } for(auto it : bus) { if(find(it.first) != find(it.second)){ ++deg[find(it.first)], ++deg[find(it.second)]; unite(it.first, it.second); } } for(int i = 1; i <= n; ++i){ if(find(i) == i && deg[i] == (nn - 1)) ans += sz[find(i)]; } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...