Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2018
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n;
  6. vector<pair<string, string>> a;
  7. vector<int> d;
  8.  
  9. void normalize (string &s)
  10. {
  11.     for (int i = 0; i < s.length(); i++)
  12.         if (s[i] >= 'A' && s[i] <= 'Z')
  13.             s[i] = s[i] - 'A' + 'a';
  14.  
  15. }
  16.  
  17.  
  18.  
  19. int calc (int q)
  20. {
  21.     if(d[q] != -1)
  22.         return d[q];
  23.     d[q] = 1;
  24.     for (int i = 0; i < n; i++)
  25.         if (a[i].second == a[q].first)
  26.             d[q] = max(d[q], calc(i) + 1);
  27.     return d[q];
  28. }
  29.  
  30. int main()
  31. {
  32.     cin >> n;
  33.  
  34.     a = vector<pair<string, string>> (n);
  35.  
  36.     d = vector<int> (n, -1);
  37.  
  38.     for (int i = 0; i < n; i++)
  39.     {
  40.         string s1, s2, s3;
  41.         cin >> s1 >> s2 >> s3;
  42.  
  43.         normalize(s1);
  44.         normalize(s3);
  45.         a[i] = {s1, s3};
  46.     }
  47.  
  48.     int result = 1;
  49.  
  50.     for (int i = 0; i < n; i++)
  51.         if (a[i].second == "polycarp")
  52.             result = max(result, calc(i) + 1);
  53.  
  54.     cout << result << endl;
  55.  
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement