Advertisement
pedrocasdev

Untitled

Sep 9th, 2022
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6.  
  7. #define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
  8. typedef long long ll;
  9. const long long mod = 1000000007;
  10. ll gcd (ll a, ll b) {return b==0 ? a : gcd(b, a%b);}
  11.  
  12. #define all(c) (c).begin(),(c).end()
  13. #define pb push_back
  14. #define mp make_pair
  15. #define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
  16. #define debug_vector(v, n) for(int i = 0; i<n; i++)cout<< v[i] << " \n"[i == n-1]
  17. #define forn(i, n) for (int i = 0; i < n; i++)
  18.  
  19. const int di4[] = {-1, 0, 1,  0};
  20. const int dj4[] = { 0, 1, 0, -1};
  21. const int di8[] = {-1, 0, 1,  0, -1, 1,-1,1};
  22. const int dj8[] = { 0, 1, 0, -1, -1, 1,1,-1};
  23. struct hash_pair {
  24.     template <class T1, class T2>
  25.     size_t operator()(const pair<T1, T2>& p) const
  26.     {
  27.         auto hash1 = hash<T1>{}(p.first);
  28.         auto hash2 = hash<T2>{}(p.second);
  29.  
  30.         if (hash1 != hash2) {
  31.             return hash1 ^ hash2;
  32.         }
  33.  
  34.          return hash1;
  35.     }
  36. };
  37. const int maxn = 2e5;
  38. bool vis[maxn];
  39. vector<vector<int>> g(26);
  40. void dfs(int u){
  41.     vis[u] = true;
  42.     for(auto v : g[u]){
  43.         if(vis[v] == false)
  44.             dfs(v);
  45.     }
  46. }
  47.  
  48. int main()
  49. {
  50. #ifdef LOCAL
  51.     freopen("input.txt", "rt", stdin);
  52.     freopen("output.txt", "wt", stdout);
  53. #endif
  54.     fastio
  55.     int tc = 1;
  56.     cin >> tc;
  57.     while(tc--){
  58.         string s;
  59.         memset(vis, false, sizeof vis);
  60.         g = vector<vector<int>> (26);
  61.         auto cc = [&](string c){
  62.             int comp = 0;
  63.             for(auto x : c){
  64.                 if(isalnum(x)){
  65.                     if(vis[x - 'A'] == false){
  66.                         dfs(x - 'A');
  67.                         comp++;
  68.                     }
  69.                 }
  70.             }
  71.             return comp;
  72.         };
  73.         while(cin >> s && s[0] != '*'){
  74.             int u = s[1] - 'A', v = s[3] -'A';
  75.             g[u].pb(v);
  76.             g[v].pb(u);
  77.         }
  78.         cin >> s;
  79.         int count_acorn = 0;
  80.         for(auto x : s){
  81.             if(isalnum(x)){
  82.                 if(g[x - 'A'].size() == 0){
  83.                     count_acorn++;
  84.                 }
  85.             }
  86.         }
  87.         int ans = cc(s);
  88.         cout << "There are "<<ans - count_acorn<< " tree(s) and "<<count_acorn<<" acorn(s)."<<endl;
  89.        
  90.     }
  91.     return 0;
  92. }
  93.  
  94.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement