제출 #498208

#제출 시각아이디문제언어결과실행 시간메모리
498208KiprasMonthly railway pass (LMIO18_menesinis_bilietas)C++14
65 / 100
3058 ms52056 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; set<int> all; for(int i = 1; i <= n; i++){ all.insert(find(i)); } int intToInd[maxN]; int cur=0; for(auto i : all){ intToInd[i]=cur; cur++; } for(int i = 1; i <= n; i++){ if(checkedContainer[find(i)])continue; int ss=s[find(i)]; bool checked[all.size()+1]={0}; for(auto x : routes[find(i)]){ if(!same(i, x)&&!checked[intToInd[find(x)]]){ ss+=s[find(x)]; } checked[intToInd[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...