Submission #706513

#TimeUsernameProblemLanguageResultExecution timeMemory
706513tamyteMonthly railway pass (LMIO18_menesinis_bilietas)C++14
100 / 100
385 ms30988 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[x].push_back(y); adj[y].push_back(x); } // cout << free << "\n"; if (free) { bool connected = true; // cerr << "a"; // cout << "a"; for (int i = 0; i < n; ++i) { if (dsu.get(i) != dsu.get(0)) { 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()) { sort(curr.begin(), curr.end()); auto it = unique(curr.begin(), curr.end()); curr.erase(it, curr.end()); int sum = (dsu.e[i] < 0 ? -dsu.e[i] : 1); for (auto& u : curr) { sum += -dsu.e[u]; } cnt += (sum == n) * (dsu.e[i] < 0 ? -dsu.e[i] : 1); } } 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...