Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.06 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6. typedef long double ld;
  7.  
  8. #define fr first
  9. #define sc second
  10. #define pb push_back
  11. #define pii pair<int, int>
  12. #define mp make_pair
  13.  
  14. const int maxn = 1e5 + 88;
  15.  
  16. const int inf = 1e9 + 88;
  17. const ll infll = 1e18 + 88;
  18. const ld PI = acos(-1);
  19. const ld eps = 1e-9;
  20. const ll mod = 1e9;
  21.  
  22. map<pair<string, int>, int> names;
  23. vector<pair<string, int> > namest;
  24. map<string, pair<int, int> > zv;
  25. int nn = 1;
  26.  
  27. int n;
  28.  
  29. vector<int> gr[maxn];
  30. bool used[maxn];
  31.  
  32. int addpr(string s, int v)
  33. {
  34. if (names[{s, v}] == 0)
  35. {
  36. names[{s, v}] = nn;
  37. nn++;
  38. namest.pb({s, v});
  39. return nn - 1;
  40. }
  41. else
  42. return names[{s, v}];
  43. }
  44.  
  45. pair<string, int> getv(int v)
  46. {
  47. return namest[v - 1];
  48. }
  49.  
  50. string pcp;
  51.  
  52. void bfs()
  53. {
  54. map<string, pair<int, int> > vr;
  55. queue<pair<int, int> > q;
  56. q.push({1, 1});
  57. while (q.size())
  58. {
  59. auto v = q.front();
  60. q.pop();
  61. vr.clear();
  62. for (int tv : gr[v.fr])
  63. {
  64. auto ttv = getv(tv);
  65. if (vr[ttv.fr].fr < ttv.sc)
  66. {
  67. vr[ttv.fr] = {ttv.sc, tv};
  68. }
  69. }
  70. for (auto tv : vr)
  71. {
  72. if (tv.fr != pcp)
  73. {
  74. if (!zv.count(tv.fr) || (zv[tv.fr].sc == v.sc && zv[tv.fr].fr < tv.sc.fr))
  75. {
  76. zv[tv.fr] = {tv.sc.fr, v.sc};
  77. q.push({tv.sc.sc, v.sc + 1});
  78. }
  79. }
  80. }
  81. }
  82. }
  83.  
  84. void solve()
  85. {
  86. cin >> n;
  87. for (int i = 0; i < n; i++)
  88. {
  89. string tn;
  90. int v;
  91. cin >> tn >> v;
  92. if (i == 0)
  93. pcp = tn;
  94. int nv = addpr(tn, v);
  95. int tc;
  96. cin >> tc;
  97. for (int j = 0; j < tc; j++)
  98. {
  99. cin >> tn >> v;
  100. gr[nv].pb(addpr(tn, v));
  101. }
  102. }
  103. bfs();
  104. cout << zv.size() << endl;
  105. vector<pair<string, int> > tt;
  106. for (auto t : zv)
  107. {
  108. tt.pb({t.fr, t.sc.fr});
  109. }
  110. sort(tt.begin(), tt.end());
  111. for (int i = 0; i < tt.size(); i++)
  112. cout << tt[i].fr << " " << tt[i].sc << "\n";
  113. }
  114.  
  115. /*struct bornode
  116. {
  117. int per[26];
  118. };
  119.  
  120. vector<bornode> bor;
  121.  
  122. int borcount(const string &p)
  123. {
  124. int nn = 0;
  125. for (int i = 0; i < p.size(); i++)
  126. {
  127. if (bor[nn].per[p[i] - 'a'] == -1)
  128. return 0;
  129. else
  130. nn = bor[nn].per[p[i] - 'a'];
  131. }
  132. for (int i = 0; i < 26; i++)
  133. if (bor[nn].per[i] != -1)
  134. return 2;
  135. return 1;
  136. }
  137.  
  138. bornode getnewbornode()
  139. {
  140. bornode t;
  141. for (int i = 0; i < 26; i++)
  142. t.per[i] = -1;
  143. return t;
  144. }
  145.  
  146. void addbor(const string &s)
  147. {
  148. int nn = 0;
  149. for (int i = 0; i < s.size(); i++)
  150. {
  151. if (bor[nn].per[s[i] - 'a'] != -1)
  152. nn = bor[nn].per[s[i] - 'a'];
  153. else
  154. {
  155. bor.pb(getnewbornode());
  156. bor[nn].per[s[i] - 'a'] = bor.size() - 1;
  157. nn = bor.size() - 1;
  158. }
  159. }
  160. }
  161.  
  162.  
  163. string prep = ".,?!'- \n";
  164.  
  165. bool isprep(char c)
  166. {
  167. for (int i = 0; i < prep.size(); i++)
  168. if (prep[i] == c)
  169. return 1;
  170. return 0;
  171. }
  172.  
  173. void solve()
  174. {
  175. bor.pb(getnewbornode());
  176. string s;
  177. int ans = 0;
  178. char c;
  179. int st = 0;
  180. string w = "";
  181. while (cin.get(c))
  182. {
  183. case 0:
  184. if (isprep(c))
  185. {
  186. ans++;
  187. }
  188. else
  189. {
  190. w += c;
  191. st = 1;
  192. /*if (borcount(w) == 1)
  193. {
  194. ans++;
  195. ans++;
  196. }
  197. else
  198. {
  199. ans += w.size();
  200. }
  201. addbor(w);
  202. }
  203. break;
  204. case 1:
  205.  
  206. break;
  207. }
  208. cout << ans << endl;
  209. }*/
  210.  
  211. int main()
  212. {
  213. freopen("input.txt", "r", stdin);
  214. srand(time(NULL));
  215. ios_base::sync_with_stdio(0);
  216. cin.tie(0);
  217. cout.tie(0);
  218. solve();
  219. return 0;
  220. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement