Salvens

H

Jul 27th, 2023
875
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. #include <array>
  2. #include <iostream>
  3. #include <vector>
  4. #include <map>
  5. #include <queue>
  6.  
  7. using namespace std;
  8.  
  9. #define int long long
  10.  
  11. const long long INF = 1e18 + 7;
  12. const int MAXN = 2e5 + 10;
  13. const int N = 2e5;
  14.  
  15. signed main() {
  16.     ios_base::sync_with_stdio(false);
  17.     cin.tie(nullptr);
  18.     cout.tie(nullptr);
  19.     int n;
  20.     cin >> n;
  21.     map<string, vector<string>> mp;
  22.     for (int i = 0; i < n; ++i) {
  23.         string name1, rep, name2;
  24.         cin >> name1 >> rep >> name2;
  25.         for (auto& elem: name1) {
  26.             elem = tolower(elem);
  27.         }
  28.         for (auto& elem: name2) {
  29.             elem = tolower(elem);
  30.         }
  31.         mp[name2].emplace_back(name1);
  32.     }
  33.  
  34.     map<string, int> d;
  35.     queue<string> q;
  36.     string root = "polycarp";
  37.     q.push(root);
  38.     d[root] = 1;
  39.     int ans = 0;
  40.     while (!q.empty()) {
  41.         string name = q.front();
  42.         q.pop();
  43.         for (const auto& to: mp[name]) {
  44.             if (d[to] == 0) {
  45.                 d[to] = d[name] + 1;
  46.                 q.push(to);
  47.                 ans = max(ans, d[to]);
  48.             }
  49.         }
  50.     }
  51.     cout << ans << '\n';
  52. }
Advertisement
Add Comment
Please, Sign In to add comment