Submission #1237022

#TimeUsernameProblemLanguageResultExecution timeMemory
1237022i_love_mritiMonthly railway pass (LMIO18_menesinis_bilietas)C++20
10 / 100
186 ms3908 KiB
#include <bits/stdc++.h> using namespace std; const int mxN = 5e5 + 100; int par[mxN], sz[mxN], deg[mxN], par2[mxN], sz2[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 find2(int u){ return u == par2[u] ? u : par2[u] = find2(par2[u]); } void unite2(int u, int v){ u = find2(u), v = find2(v); if(u == v) return; par2[u] = v, sz2[v] += sz2[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) && find2(it.first) != find2(it.second)){ ++deg[find(it.first)], ++deg[find(it.second)]; //unite(it.first, it.second); unite2(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...