Submission #805715

#TimeUsernameProblemLanguageResultExecution timeMemory
805715YesPyMonthly railway pass (LMIO18_menesinis_bilietas)C++17
100 / 100
311 ms28800 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define tcT template<class T #define fastio ios::sync_with_stdio(false);cin.tie(nullptr); #define ln '\n' #define nwln cout<<ln; using namespace std; tcT> using vr = vector<T>; using pi = pair<int, int>; using vi = vr<int>; using vpi = vr<pi>; #define fri(i,a,b) for(int i=(a); i<(b); ++i) #define each(x, a) for(auto& x: a) #define sz(x) int((x).size()) #define phb push_back #define eb emplace_back const int MX = (int) 5e5+3; int N, M, par[MX], len[MX], deg[MX], ans; vpi bus; vi fathers; inline int find(int u) { if(par[u] == u) return u; return par[u] = find(par[u]); } void uni(int u, int v) { u = find(u), v = find(v); if(u == v) return; if(len[u] < len[v]) swap(u, v); par[v] = u, len[u] += len[v]; } int main() { fastio cin>>N>>M; fri(i,1,N+1) par[i] = i, len[i] = 1; while(M--) { int u, v; char ty; cin>>u>>v>>ty; if(ty == 'A') bus.eb(u, v); else uni(find(u), find(v)); } fri(i,1,N+1) { if(par[i] == i) fathers.eb(i); } set<pi> orz; each(z, bus) { z.ff = find(z.ff), z.ss = find(z.ss); if(z.ff == z.ss) continue; orz.insert(z); } each(z, orz) ++deg[z.ff], ++deg[z.ss]; each(x, fathers) { if(deg[x] == sz(fathers)-1) ans += len[x]; } cout<<ans<<ln; 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...