Submission #706507

#TimeUsernameProblemLanguageResultExecution timeMemory
706507tamyteMonthly railway pass (LMIO18_menesinis_bilietas)C++14
6 / 100
679 ms50164 KiB
#include <bits/stdc++.h> using namespace std; struct DSU { vector<int> e; DSU(int n) { e = vector<int>(n, -1); } int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } bool same(int x, int y) { return get(x) == get(y); } int size(int x) { return -e[get(x)]; } bool unite(int x, int y) { // cout << x << " " << y << " -> "; x = get(x), y = get(y); // cout << x << " " << y << "\n"; if (x == y) return false; if (e[x] > e[y]) swap(x, y); e[x] += e[y]; e[y] = x; // cout << x << " " << y << "\n"; return true; } }; vector<int> adj[(int)5e5 + 1]; int main() { int n, m; cin >> n >> m; DSU dsu(n); if (!m) { cout << 0; return 0; } vector<pair<int, int>> bus; for (int i = 0; i < m; ++i) { int a, b; char c; cin >> a >> b >> c; --a; --b; if (c == 'T') { // cout << "a"; dsu.unite(a, b); } else { bus.push_back({a, b}); } } // for (auto u : dsu.e) { // cout << u << " "; // } // cout << "\n"; bool free = true; for (auto u : bus) { int x = dsu.get(u.first); int y = dsu.get(u.second); if (x == y) continue; free = false; adj[u.first].push_back(u.second); adj[u.second].push_back(u.first); } if (free) { bool connected = true; // cerr << "a"; for (auto& p : dsu.e) { if (dsu.get(p) != dsu.e.front()) { connected = false; break; } } if (connected) cout << n; else cout << 0; return 0; } // cerr << "a"; int cnt = 0; for (int i = 0; i < n; ++i) { auto& curr = adj[i]; if (curr.size()) { set<int> st; int x = dsu.get(i); st.insert(x); int sum = -dsu.e[x]; for (auto& u : curr) { int y = dsu.get(u); if (!st.count(y)) { st.insert(y); sum += -dsu.e[y]; } } cnt += (sum == n) * (-dsu.e[x]); } } cout << cnt; }
#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...