Submission #1237008

#TimeUsernameProblemLanguageResultExecution timeMemory
1237008i_love_mritiMonthly railway pass (LMIO18_menesinis_bilietas)C++20
6 / 100
399 ms24228 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}); } for(auto it : bus) ++deg[find(it.first)], ++deg[find(it.second)]; for(int i = 1; i <= n; ++i){ if(find(i) == i && deg[i] == (n - 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...