Submission #642829

#TimeUsernameProblemLanguageResultExecution timeMemory
642829JvThunderMonthly railway pass (LMIO18_menesinis_bilietas)C++14
100 / 100
366 ms27372 KiB
// JvThunder ORZ Template #include <bits/stdc++.h> #define pb push_back #define F first #define S second #define pii pair<int,int> typedef long long ll; using namespace std; const int N = 5e5+5; int n,m; int par[N]; int sz[N]; int deg[N]; vector<pii> train; vector<pii> bus; int find(int x) { if(par[x]==x) return x; return par[x] = find(par[x]); } void join(int a,int b) { int ra = find(a); int rb = find(b); if(ra==rb) return; par[rb] = ra; sz[ra] += sz[rb]; sz[rb] = 0; } void solve() { cin >> n >> m; for(int i=0;i<m;i++) { int a,b; char type; cin >> a >> b >> type; if(type=='T') train.pb({a,b}); else bus.pb({a,b}); } for(int i=1;i<=n;i++) par[i] = i, sz[i] = 1; for(auto x:train) join(x.F,x.S); int cc = 0; for(int i=1;i<=n;i++) if(par[i]==i) cc++; set<pii> s; for(auto x:bus) { int a = find(x.F); int b = find(x.S); if(a==b) continue; s.insert({min(a,b),max(a,b)}); } for(auto x:s) { int a = x.F; int b = x.S; deg[a]++; deg[b]++; } int ans = 0; for(int i=1;i<=n;i++) { if(i==par[i]) { if(deg[i]==cc-1) ans += sz[i]; } } cout << ans << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); 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...