제출 #850909

#제출 시각아이디문제언어결과실행 시간메모리
850909pakapuMonthly railway pass (LMIO18_menesinis_bilietas)C++17
16 / 100
345 ms62224 KiB
#include <bits/stdc++.h> using namespace std; set<int> used_cc; vector<int> used; vector<int> cc_size; vector<int> distribute_used; vector<int> answer_used; vector<int> cc_leader; vector<vector<int>> bus_g; vector<vector<int>> train_g; int calculate_cc_size(int u, int leader) { cc_leader[u] = leader; used[u] = true; int curr_size = 1; for(auto v : train_g[u]) { if(used[v]) { continue; } curr_size += calculate_cc_size(v, leader); } return curr_size; } int calculate_cheap_routes(int u) { answer_used[u] = true; int ans = 0; for(auto v : train_g[u]) { if(answer_used[v]) { continue; } ans += calculate_cheap_routes(v); } for(auto v : bus_g[u]) { if(used_cc.count(cc_leader[v])) { continue; } used_cc.insert(cc_leader[v]); ans += cc_size[cc_leader[v]]; } return ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; bus_g = vector<vector<int>>(n); train_g = vector<vector<int>>(n); for(int i = 0; i < m; i++) { int from, to; char type; cin >> from >> to >> type; from--; to--; if(type == 'T') { train_g[to].push_back(from); train_g[from].push_back(to); } if(type == 'A') { bus_g[to].push_back(from); bus_g[from].push_back(to); } } cc_leader = vector<int>(n, -1); used = vector<int>(n); cc_size = vector<int>(n); distribute_used = vector<int>(n); for(int i = 0; i < n; i++) { if(!used[i]) { int curr = calculate_cc_size(i, i); cc_size[cc_leader[i]] = curr; } } // Calculate the number of reachable cities for every node int ans = 0; answer_used = vector<int>(n); vector<int> cheap_cities(n); for(int i = 0; i < n; i++) { if(!answer_used[i]) { used_cc.clear(); //assert(cc_leader[i] != -1); cheap_cities[cc_leader[i]] = cc_size[cc_leader[i]] + calculate_cheap_routes(i); assert(cheap_cities[cc_leader[i]] <= n); } } for(int i = 0; i < n; i++) { assert(cc_leader[i] != -1); if(cheap_cities[cc_leader[i]] == n) { ans++; } } 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...