http://ybt.ssoier.cn:8088/problem_show.php?pid=1388

方法一：普通模拟，时间复杂度O（50000*1000）只能拿40分

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string s;
 4 string pep[50010];//存放名字 
 5 int fa[50010];//记录他的祖先，默认值为0时本人就是祖先 
 6 
 7 int main()
 8 {
 9     int i=0;
10     int f=-1;
11     while(1){
12         cin>>s;
13         if(s.length()==1 && s=="$")break;//结束条件 
14         if(s[0]=='#'){//如果是父亲 
15             int t=0; //判断是否已经存在 
16             for(int j=1; j<=i; j++){//从家谱中找 
17                 if(pep[j]==s.substr(1)){
18                     t=j; break;
19                 }
20             }
21             if(!t){//如果不在家谱中，插入 
22                 i++;
23                 pep[i]=s.substr(1);
24                 f=i;
25             }
26             else//在家谱中，记录他的位置下标 
27                 f=t;
28         }
29         if(s[0]=='+'){//如果是孩子 
30             i++;
31             pep[i]=s.substr(1);//插入到家族 
32 //            cout<<i<<":"<<pep[i]<<endl;
33             while(fa[f])f=fa[f];//寻找这个孩子的祖先 
34             fa[i]=f;//标记祖先下标 
35         }
36         if(s[0]=='?'){
37             
38             int t;
39             cout<<s.substr(1)<<" ";
40             for(int j=1; j<=i; j++){//查找存储下标 
41                 if(pep[j]==s.substr(1)){
42                     t=j; break;
43                 }
44             }
45             if(fa[t]==0)cout<<pep[t]<<endl;//如果祖先是0说明就是祖先 
46             else cout<<pep[fa[t]]<<endl;//否则输出祖先 
47         }
48     }
49     return 0;
50 } 

方法一：