제출 #805723

#제출 시각아이디문제언어결과실행 시간메모리
805723HD1Monthly railway pass (LMIO18_menesinis_bilietas)C++14
100 / 100
689 ms101616 KiB
// we all are lost trying to be someone. #include <bits/stdc++.h> #define fastio ios_base::sync_with_studio(0); cin.tie(0); #define sz(x) ll(x.size()) #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define pb push_back #define ss second #define ff first using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> ii; const int MAX=1e6; const int inf=1e9; const int mod=1e9+7; vector<ll> gfo1[MAX]; vector<ll> gfo2[MAX]; vector<ii> s; vector<ll> c; bool vst[MAX]; ll tam[MAX], p[MAX]; set<ii> z; void dfsmark(ll u, ll x){ p[u]=x; tam[x]++; vst[u]=true; for(ll v:gfo1[u]){ if(!vst[v]){ dfsmark(v,x); } } } void solve(){ ll n, m, u, v; char x; cin>>n>>m; for(ll i=0; i<m; i++){ cin>>u>>v>>x; if(x=='A'){ s.pb({u,v}); } else{ gfo1[u].pb(v); gfo1[v].pb(u); } } ll cont=1; for(ll i=1; i<=n; i++){ if(!vst[i]) { dfsmark(i,cont); cont++; } } cont--; if(cont==1){ cout<<n<<endl; return; } for(ii x:s){ u=p[x.ff]; v=p[x.ss]; if(u!=v && !(z.count({min(u,v),max(u,v)}))){ gfo2[u].pb(v); gfo2[v].pb(u); z.insert({min(u,v),max(u,v)}); } } ll ans=0; for(ll i=1; i<=cont; i++){ if(sz(gfo2[i])==cont-1)ans+=tam[i]; } cout<<ans<<endl; return; } int main(){ 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...