fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pil pair<int,ll>
  14. #define pli pair<ll,int>
  15. #define MOD 1000000007
  16. #define el "\n"
  17. #define MAX 204
  18.  
  19. int n;
  20. string s[MAX];
  21. vector<int> adj[MAX];
  22. vector<string> name;
  23.  
  24. void pre(string &str)
  25. {
  26.     string tmp;
  27.     foru(i,0,str.size()-1)
  28.     {
  29.         if(isalpha(str[i]) && isupper(str[i])) str[i]=tolower(str[i]);
  30.         if(i==str.size()-1) 
  31.         {
  32.             tmp+=str[i];
  33.             name.pb(tmp);
  34.             continue;
  35.         }
  36.         if(str[i]==' ')
  37.         {
  38.             if(tmp!="reposted") name.pb(tmp);
  39.             tmp="";
  40.         }
  41.         else tmp+=str[i];
  42.     }
  43. }
  44.  
  45. void xuli(string str)
  46. {
  47.     int u,v;
  48.     string tmp="";
  49.     foru(i,0,str.size()-1)
  50.     {
  51.         if(i==str.size()-1) 
  52.         {
  53.             tmp+=str[i];
  54.             u=lower_bound(name.begin(),name.end(),tmp)-name.begin()+1;
  55.             continue;
  56.         }
  57.         if(str[i]==' ')
  58.         {
  59.             if(tmp!="reposted") 
  60.             {
  61.                 v=lower_bound(name.begin(),name.end(),tmp)-name.begin()+1;
  62.             }
  63.             tmp="";
  64.         }
  65.         else tmp+=str[i];
  66.     }
  67.     adj[u].pb(v);
  68. }
  69.  
  70. int ans=0;
  71. int dist[MAX];
  72.  
  73. void bfs(int u)
  74. {
  75.     queue<int> q;
  76.     q.push(u);
  77.     memset(dist,-1,sizeof(dist));
  78.     dist[u]=1;
  79.     while(!q.empty())
  80.     {
  81.         int v=q.front(); q.pop();
  82.         for(int k:adj[v])
  83.         {
  84.             if(dist[k]==-1)
  85.             {
  86.                 dist[k]=dist[v]+1;
  87.                 ans=max(ans,dist[k]);
  88.                 q.push(k);
  89.             }
  90.         }
  91.     }
  92. }
  93.  
  94. void calc()
  95. {
  96.     sort(name.begin(),name.end());
  97.     name.erase(unique(name.begin(),name.end()),name.end());
  98.     foru(i,1,n) xuli(s[i]);
  99.     int u=lower_bound(name.begin(),name.end(),"polycarp")-name.begin()+1;
  100.     bfs(u);
  101.     cout<<ans;
  102. }
  103.  
  104. int main()
  105. {
  106.     fastio
  107.     #ifndef ONLINE_JUDGE
  108.     freopen(FILE ".inp","r",stdin);
  109.     freopen(FILE ".out","w",stdout);
  110.     #endif // ONLINE_JUDGE
  111.  
  112.     cin>>n; cin.ignore();
  113.     foru(i,1,n)
  114.     {
  115.         getline(cin,s[i]);
  116.         pre(s[i]);
  117.     }
  118.     calc();
  119.  
  120.     return 0;
  121. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hwRd7R
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!