fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3.  
  4.  
  5. using namespace std;
  6.  
  7. static string toLower(const string &s) { string res = s; for (char &c : res) c = tolower(c); return res; }
  8.  
  9. int main() { ios::sync_with_stdio(false); cin.tie(NULL);
  10.  
  11. int N;
  12. if (!(cin >> N)) return 0;
  13.  
  14. struct Person { string name, parent; bool alive; };
  15. vector<Person> members;
  16. members.reserve(N);
  17. unordered_map<string, string> nameMap; // lower-case -> original
  18.  
  19. for (int i = 0; i < N; i++) {
  20.     string name, parent, isAlive;
  21.     cin >> name >> parent >> isAlive;
  22.     bool alive = (isAlive == "true" || isAlive == "True");
  23.     members.push_back({name, parent, alive});
  24.     nameMap[toLower(name)] = name;
  25. }
  26.  
  27. // Build children map and identify root
  28. unordered_map<string, vector<string>> children;
  29. string root;
  30. for (auto &p : members) {
  31.     if (toLower(p.parent) == "null") {
  32.         root = p.name;
  33.     } else {
  34.         string key = toLower(p.parent);
  35.         auto it = nameMap.find(key);
  36.         if (it != nameMap.end()) {
  37.             children[it->second].push_back(p.name);
  38.         }
  39.         else {
  40.             // Parent not found; ignore or could handle error
  41.         }
  42.     }
  43. }
  44.  
  45. vector<string> succession;
  46. succession.reserve(3);
  47.  
  48. // Iterative preorder DFS
  49. stack<string> st;
  50. if (!root.empty()) st.push(root);
  51.  
  52. while (!st.empty() && succession.size() < 3) {
  53.     string u = st.top(); st.pop();
  54.     // Find alive status from members list or map
  55.     // We can build aliveMap
  56.  
  57.     // Build alive map first
  58.     static unordered_map<string, bool> aliveMap;
  59.     if (aliveMap.empty()) {
  60.         for (auto &p : members) aliveMap[p.name] = p.alive;
  61.     }
  62.  
  63.     if (aliveMap[u]) {
  64.         succession.push_back(u);
  65.         if (succession.size() == 3) break;
  66.     }
  67.  
  68.     auto it = children.find(u);
  69.     if (it != children.end()) {
  70.         // push in reverse birth order: children were inserted in input order
  71.         for (auto rit = it->second.rbegin(); rit != it->second.rend(); ++rit) {
  72.             st.push(*rit);
  73.         }
  74.     }
  75. }
  76.  
  77. for (auto &name : succession) cout << name << ' ';
  78. return 0;
  79.  
  80. }
  81.  
  82.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
8
Elizabeth null false
Charles elizabeth true
Anne Elizabeth true
Andrew Elizabeth true
Edward Elizabeth true
William Charles true
Harry Charles true
George William true
stdout 
Charles William George
https://ideone.com/Oy5UaS
language:
C++14 (gcc 8.3)
created:
3 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!