Submission #382152

#	Time	Username	Problem	Language	Result	Execution time	Memory
382152		mohamedsobhi777	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	100 / 100	284 ms	40052 KiB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound

using ll = long long;
using ld = long double;

const int N = 5e5 + 7;
const ll mod = 1e9 + 7;

int n, m;
vii e;
vi adj[N];

struct dsu
{
       int fat[N];
       int cnt[N] ;
       int comp = 0;
       dsu()
       {
              fill(cnt , cnt + N , 1) ;
              iota(fat, fat + N, 0);
       }
       void link(int u, int v)
       {
              u = find(u);
              v = find(v);
              if(u != v){
                     ++ comp ; 
                     cnt[v] += cnt[u] ; 
                     cnt[u] = 0 ; 
                     fat[u] = v; 
              }
       }

       int find(int x)
       {
              return fat[x] = x == fat[x] ? x : find(fat[x]);
       }

} d1, d2;

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> n >> m;
       for (int i = 0; i < m; ++i)
       {
              int u, v;
              char c;
              cin >> u >> v >> c;
              if (c == 'T')
              {
                     d1.link(u, v);
              }
              else
              {
                     e.pb({u, v});
              }
              d2.link(u, v);
       }

       if (d2.comp != n - 1)
              return cout << 0, 0;

       int ans = 0;  


       if (e.empty())
       {
              return cout << n, 0;
       }
       else
       {
              for (auto u : e)
              {
                     int v1 = d1.find(u.f);
                     int v2 = d1.find(u.s);
                     if (v1 != v2)
                     {
                            adj[v1].pb(v2);
                            adj[v2].pb(v1);
                     }
              }
              for(int i =1 ;i <= n;++ i){
                     sort(all(adj[i])) ; 
                     adj[i].erase(unique(all(adj[i])) , adj[i].end()) ;
              }
              int ac = n - d1.comp ;

              for(int i = 1;i <= n;++ i){
                     if(sz(adj[i]) == ac - 1){
                            ans += d1.cnt[ i ] ;
                     }
              }
              cout << ans ;
       }

       return 0;
}

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