fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iomanip>
  6. #include <numeric>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <string>
  11.  
  12. #define hyathu main
  13. #define popcorn __builtin_popcount
  14.  
  15. using namespace std;
  16. using ll = long long;
  17. using ull = unsigned long long;
  18. using ld = long double;
  19. using pint = int*;
  20.  
  21. constexpr int mmb = 2e5 + 69;
  22. const ld pi = atan(1) * 4;
  23.  
  24. int t, n, cnt;
  25.  
  26. string s[mmb];
  27. pair <string, string> q[mmb];
  28.  
  29. vector <int> v[mmb], o[mmb];
  30. int d[mmb], deg[mmb], ct[mmb];
  31.  
  32. void reset(){
  33.     for(int i = 1; i <= n; ++i)
  34.         v[i].clear(),
  35.         o[i].clear();
  36.     cnt = 0;
  37. }
  38.  
  39. void readData(){
  40.     cin >> n;
  41.     for(int i = 1; i <= n; ++i){
  42.         cin >> q[i].first >> q[i].second;
  43.         s[++cnt] = q[i].first;
  44.         s[++cnt] = q[i].second;
  45.     }
  46.  
  47.     sort(s + 1, s + cnt + 1);
  48.     cnt = unique(s + 1, s + cnt + 1) - s - 1;
  49.     fill(deg + 1, deg + n + 1, 0);
  50.     for(int i = 1; i <= n; ++i){
  51.         int x = lower_bound(s + 1, s + cnt + 1, q[i].first) - s;
  52.         int y = lower_bound(s + 1, s + cnt + 1, q[i].second) - s;
  53. //        cout << x << " " << y << "\n";
  54.         v[y].push_back(x);
  55.         o[x].push_back(y);
  56.         ++deg[x];
  57.     }
  58. }
  59.  
  60. void solve(){
  61.     fill(d + 1, d + cnt + 1, 0);
  62.  
  63.     queue <int> qe;
  64.     for(int i = 1; i <= cnt; ++i){
  65.         if(deg[i] == 0){
  66.             d[i] = 2;
  67.             qe.push(i);
  68.         }
  69.     }
  70.  
  71.     while(!qe.empty()){
  72.         int p = qe.front();
  73.         qe.pop();
  74.  
  75.         for(int i : v[p]){
  76.             if(d[i] != 0)
  77.                 continue;
  78.  
  79.             if(d[p] == 2){
  80.                 d[i] = 1;
  81.                 qe.push(i);
  82.                 continue;
  83.             }
  84.  
  85.             ++ct[i];
  86.             if(ct[i] == deg[i]){
  87.                 d[i] = 2;
  88.                 qe.push(i);
  89.                 continue;
  90.             }
  91.         }
  92.     }
  93.  
  94. //    for(int i = 1; i <= n; ++i)
  95. //        cout << d[i] << " ";
  96. //    cout << "\n";
  97.  
  98.     for(int i = 1; i <= n; ++i){
  99.         if(d[i] != 1) continue;
  100.         for(int j : o[i]){
  101.             if(d[j] == 2 && deg[j] > 0){
  102.                 cout << "Quang\n";
  103.                 return;
  104.             }
  105.         }
  106.     }
  107.  
  108.     if(count(d + 1, d + n + 1, 0) > 0){
  109.         cout << "Hoa\n";
  110.         return;
  111.     }
  112.  
  113.     cout << "Hieu\n";
  114. }
  115.  
  116. #define filename "test"
  117.  
  118. int hyathu(){
  119.     ios_base::sync_with_stdio(false);
  120.     cin.tie(NULL);
  121.     cout.tie(NULL);
  122.  
  123.     #ifdef dangheo
  124.     freopen("test.inp", "r", stdin);
  125.     //freopen("test.out", "w", stdout);
  126.     #else
  127.     //freopen(filename".INP", "r", stdin);
  128.     //freopen(filename".OUT", "w", stdout);
  129.     #endif
  130.     cin >> t;
  131.     while(t--){
  132.         reset();
  133.         readData();
  134.         solve();
  135.     }
  136.  
  137.     return 0;
  138. }
  139.  
Success #stdin #stdout 0.01s 32304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SzjIXt
language:
C++ (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!