제출 #498190

#제출 시각아이디문제언어결과실행 시간메모리
498190KiprasMonthly railway pass (LMIO18_menesinis_bilietas)C++14
65 / 100
3068 ms45548 KiB
#include <bits/stdc++.h> using namespace std; const int maxN = 1e5*5+1; int n, m; vector<pair<bool, int>> adj[maxN]; int par[maxN]; int s[maxN]; vector<int> routes[maxN]; bool checkedContainer[maxN]; int find(int a){ if(par[a]==a)return a; return par[a]=find(par[a]); } void unite(int a, int b){ a = find(a), b = find(b); if(a==b)return; par[b]=a; s[a]+=s[b]; } bool same(int a, int b){ return find(a)==find(b); } int main() { ios_base::sync_with_stdio(0);cin.tie(nullptr); cin>>n>>m; for(int i = 0; i < m; i++){ int a, b; char t; bool type; cin>>a>>b>>t; if(t=='A')type=0; else type=1; adj[a].push_back({type, b}); adj[b].push_back({type, a}); } for(int i = 0; i < maxN; i++)par[i]=i; for(int i = 0; i < maxN; i++)s[i]=1; for(int i = 1; i <= n; i++){ for(auto x : adj[i]){ if(x.first==0){ }else{ unite(x.second, i); } } } for(int i = 1; i <= n; i++){ for(auto x : adj[i]){ if(x.first==0){ routes[find(i)].push_back(find(x.second)); routes[find(x.second)].push_back(find(i)); }else{ } } } int ans=0; for(int i = 1; i <= n; i++){ if(checkedContainer[find(i)])continue; int ss=s[find(i)]; bool checked[maxN]; fill(checked, checked+maxN, 0); for(auto x : routes[find(i)]){ if(!same(i, x)&&!checked[find(x)]){ ss+=s[find(x)]; checked[find(x)]=1; } } if(ss==n){ ans+=s[find(i)]; checkedContainer[find(i)]=true; } } cout<<ans; 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...