Submission #1237029

#TimeUsernameProblemLanguageResultExecution timeMemory
1237029i_love_mritiMonthly railway pass (LMIO18_menesinis_bilietas)C++20
10 / 100
185 ms7748 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){ if(u == par[u]) return u; return 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){ if(u == par2[u]) return u; return par2[u] = find2(par2[u]); } void unite2(int u, int v){ u = find2(u), v = find2(v); if(u == v) return; //cout << "uni" << u << v << endl; 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, par2[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(int i = 1; i <= n; ++i) sz2[i] = sz[i], par2[i] = par[i]; for(auto it : bus) { if(find(it.first) != find(it.second) && find2(find(it.first)) != find2(find(it.second))){ ++deg[find(it.first)], ++deg[find(it.second)]; //unite(it.first, it.second); unite2(find(it.first), find(it.second)); //cout << find(it.first) << " " << find(it.second) << endl; } } //cout << sz2[find2(1)] << endl; if(sz2[find2(1)] != n){ cout << "0\n"; return 0; } //cout << nn - 1 << endl; for(int i = 1; i <= n; ++i){ if(find(i) == i && deg[i] == (nn - 1)){ ans += sz[find(i)]; //cout << i << endl; } } 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...