Submission #634667

#TimeUsernameProblemLanguageResultExecution timeMemory
634667mrkhan2000Monthly railway pass (LMIO18_menesinis_bilietas)C++17
100 / 100
642 ms71508 KiB
#include <bits/stdc++.h> #define ll long long #define MOD 1000000007 using namespace std; class union_find { private: int N; int components; vector<int> data; vector<int> deg; public: union_find(int N) : N(N), components(N), data(N, -1), deg(N, 0) {} int find(int u) { if(u >= N) return -1; while(data[u] >= 0) u = data[u]; return u; } bool unite(int u, int v) { if(u >= N || v >= N) return false; u = find(u); v = find(v); if(u == v) return false; if(data[u] > data[v]) swap(u, v); data[u] += data[v]; data[v] = u; --components; return true; } int size(int u) { return -data[find(u)]; } int getComponentsCount() { return components; } }; void solve() { int N, E; cin >> N >> E; union_find UF(N); vector<vector<int>> bcns; bcns.reserve(E); for(int i = 0; i < E; i++) { int U, V; cin >> U >> V; char T; cin >> T; --U, --V; if(T == 'T') UF.unite(U, V); else bcns.push_back({U,V}); } set<int> rep; for(int i = 0; i < N; i++) { rep.insert(UF.find(i)); } vector<int> deg(N); set<pair<int,int>> done; for(auto &cns : bcns) if( UF.find(cns[0])^UF.find(cns[1]) && done.find({UF.find(cns[0]), UF.find(cns[1])}) == done.end() ) { deg[UF.find(cns[0])]++; deg[UF.find(cns[1])]++; done.insert({UF.find(cns[0]), UF.find(cns[1])}); } set<int> work; for(auto city : rep) { if(deg[city] == UF.getComponentsCount() - 1) { work.insert(city); } } int ans = 0; for(int i = 0; i < N; i++) { if(work.find(UF.find(i)) != work.end()) { ++ans; } } cout << ans << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int test_cases = 1; // cin >> test_cases; for(int test_case = 1; test_case <= test_cases; test_case++) { // cout << "Case #" << test_case << ": "; solve(); } 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...