Advertisement
Guest User

Untitled

a guest
Feb 24th, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.39 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ALL(x) x.begin(), x.end()
  3. #define pb push_back
  4. #define ld long double
  5. typedef unsigned long long int lli;
  6. using namespace std;
  7. const lli INF =1e9+ 7;
  8. const int N =1000;
  9. pair< string, int> nodes[N+100];
  10. vector< vector< int > > g;
  11. vector< bool > us(N);
  12. map< string, int > ans;
  13. map< string, int > iter[N+100];
  14. map<string, vector< int > > pro;
  15. map< string , bool > pro_us;
  16. void bad_dfs( int x){
  17. us[x] =1;
  18. for(auto it: g[x]){
  19. if(!us[it]) bad_dfs(it);
  20. }
  21. }
  22. void try_add(int x, int i){
  23. string s= nodes[x].first;
  24. if(!iter[i].count(s)){
  25. iter[i][s] =x;
  26. }
  27. else {
  28. int v =iter[i][s];
  29. if(nodes[v].second < nodes[x].second){
  30. iter[i][s]= x;
  31. }
  32. }
  33. }
  34. void dfs( int x){
  35. iter[0][nodes[x].first] = x;
  36. for(int i(0); i<N+5; i++){
  37. for(auto it:iter[i]){
  38. if(us[it.second] )continue;
  39. ans[it.first] = it.second;
  40. for(auto jt: g[it.second]){
  41. if( !us[jt]) try_add(jt, i+1);
  42. }
  43. }
  44. for(auto it:iter[i+1]){
  45. if(!pro_us[it.first]){
  46. pro_us[it.first] = 1;
  47. for( auto kt: pro[it.first]){
  48. if(!us[kt] && kt != it.second ) bad_dfs(kt);
  49. }
  50. }
  51. }
  52. }
  53. }
  54.  
  55. int main(){
  56. freopen("in.txt", "r", stdin);
  57. int n;
  58. scanf("%d",&n);
  59. g.resize(n);
  60. vector< vector< pair< string , int > > > z(n);
  61. map< pair< string, int > , int > mt;
  62. for( int i(0); i<n; i++){
  63. cin>>nodes[i].first>> nodes[i].second;
  64. mt[nodes[i]] = i;
  65. pro[nodes[i].first].pb(i);
  66. int k;
  67. scanf("%d",&k);
  68. for( int j(0); j<k; j++){
  69. pair<string, int >tmp;
  70. cin>>tmp.first>>tmp.second;
  71. z[i].pb(tmp);
  72. }
  73. }
  74. for( int i(0); i<n; i++){
  75. for( int j(0); j<z[i].size(); j++){
  76. g[i].pb(mt[z[i][j]]);
  77. }
  78. }
  79. for( int i(0); i<n; i++) pro_us[nodes[i].first] = 0;
  80. for(auto it: pro[nodes[0].first]) if(it != 0) bad_dfs(it);
  81. dfs(0);
  82. if(ans.count(nodes[0].first)){
  83. auto it = ans.find(nodes[0].first);
  84. ans.erase(it);
  85. }
  86. printf("%d\n",ans.size());
  87. for(auto it:ans){
  88. cout<< it.first<<" "<<nodes[it.second].second<<endl;
  89. }
  90. return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement