# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
920866 | thelegendary08 | Monthly railway pass (LMIO18_menesinis_bilietas) | C++14 | 686 ms | 97252 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0;i<n;i++)
#define pb push_back
using namespace std;
const int mxn = 500005;
vector<int> adj[mxn];
bool vis[mxn];
vector<int>cur;
void dfs(int u){
if(vis[u])return;
vis[u] = 1;
cur.pb(u);
for(int x : adj[u])dfs(x);
}
int main(){
int n,m;
cin>>n>>m;
vector<pair<int,int>> bus;
f0r(i, m){
int a,b;
cin>>a>>b;
char c;
cin>>c;
if(c == 'T'){
adj[--a].pb(--b);
adj[b].pb(a);
}
else{
bus.pb({--a,--b});
}
}
f0r(i,n)vis[i] = 0;
vector<vector<int>>ccs;
f0r(i,n){
if(!vis[i]){
cur.clear();
dfs(i);
ccs.pb(cur);
}
//f0r(j,n)cout<<vis[j]<<' ';
//cout<<'\n';
//for(int x : cur)cout<<x<<' ';
//cout<<'\n';
}
int component[n];
f0r(i,ccs.size()){
for(int x : ccs[i]){
component[x] = i;
}
}
//the size of component i is just ccs[i].size()
set<int>adj[ccs.size()];
for(pair<int,int> p : bus){
int pa = p.first;
int pb = p.second;
if(component[pa] != component[pb]){
adj[component[pa]].insert(component[pb]);
adj[component[pb]].insert(component[pa]);
}
}
int ans = 0;
f0r(i,ccs.size()){
//cout<<adj[i].size()<<' ';
if(adj[i].size() == ccs.size() - 1)ans += ccs[i].size();
}
cout<<ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |