Submission #826381

#TimeUsernameProblemLanguageResultExecution timeMemory
826381OAleksaMonthly railway pass (LMIO18_menesinis_bilietas)C++14
100 / 100
425 ms62868 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; #define int long long const int maxn = 5e5 + 69; vector<int> p(maxn), sz(maxn); vector<int> deg(maxn); int find_set(int v) { if(p[v] == v) return v; return p[v] = find_set(p[v]); } void unite(int a, int b) { a = find_set(a); b = find_set(b); if(a != b) { if(sz[a] < sz[b]) swap(a, b); p[b] = a; sz[a] += sz[b]; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; while(tt--) { int n, m; cin >> n >> m; vector<pair<int, int>> edges; for(int i = 1;i <= n;i++) { p[i] = i; sz[i] = 1; } for(int i = 0;i < m;i++) { int a, b; char c; cin >> a >> b >> c; if(c == 'T') unite(a, b); else edges.push_back({a, b}); } set<int> kurac; for(int i = 1;i <= n;i++) kurac.insert(find_set(i)); int c = kurac.size(); int ans = 0; set<pair<int, int>> bio; for(auto x : edges) { int a = find_set(x.f); int b = find_set(x.s); if(a > b) swap(a, b); if(bio.count({a, b}) || a == b) continue; else { bio.insert({a, b}); deg[a]++; deg[b]++; } } for(auto x : kurac) ans += (deg[x] >= c - 1 ? sz[x] : 0); if(c == 1) ans = n; cout << ans; } 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...