제출 #1122547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122547		ardadut	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	471 ms	51124 KiB

menesinis_bilietas

#include <bits/stdc++.h>
    
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout Cikti*/

#define maxn 100005

ll n,m;
vector<vector<ll>> adj;
vector<ll> komsu_sayisi;
vector<ll> buyukluk;
vector<bool> vis;
vector<ll> component;
vector<pair<ll,ll>> bus;

inline void dfs(ll node, ll component_no){
    vis[node] = 1;
    component[node] = component_no;
    buyukluk[component_no]++;
    for(auto go : adj[node]){
        if(!vis[go]){
            dfs(go,component_no);
        }
    }
}

inline void solve(){

    cin >> n >> m;

    adj.resize(n+1);
    vis.resize(n+1,0);
    component.resize(n+1);
    buyukluk.resize(n+1,0);

    while(m--){
        ll a,b;
        char c;
        cin >> a >> b >> c;
        if(c == 'T'){
            adj[a].pb(b);
            adj[b].pb(a);
        }else{
            bus.pb({a,b});
        }
    }

    ll component_no = 1;

    for(ll i = 1 ; i <= n ; i++){
        if(!vis[i]){
            dfs(i,component_no);
            component_no++;
        }
    }

    komsu_sayisi.resize(component_no+1);
    map<pair<ll,ll>,ll> mapp;

    for(auto it : bus){
        ll a = component[it.first];
        ll b = component[it.second];
        if(a > b) swap(a,b);
        if(a != b and mapp[{a,b}] < 1){
            komsu_sayisi[a]++;
            komsu_sayisi[b]++;
            mapp[{a,b}]++;
        }
    }

    ll ans = 0;

    for(ll i = 1 ; i <= component_no-1 ; i++){
        if(komsu_sayisi[i] == component_no-2){
            ans += buyukluk[i];
        }
    }

    cout << ans << endl;

}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    
}

• Subtask 1: 10 / 10
• Subtask 2: 6 / 6
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35
• Subtask 5: 19 / 19