Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.05 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <cstdio>
  3. #include <vector>
  4. #include <string>
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <map>
  8. #include <iterator>
  9. #include <functional>
  10. #include <set>
  11. #include <stack>
  12. #include <queue>
  13. #include <deque>
  14. #include <fstream>
  15. #include <iomanip>
  16. #include <numeric>
  17. #include <cmath>
  18. #include <list>
  19. #include <sstream>
  20. #include <cstring>
  21. #include <stdio.h>
  22. using namespace std;
  23. #pragma GCC optimize("O3")
  24. #pragma GCC target("sse4")
  25.  
  26. typedef long double LD;
  27. typedef long long LL;
  28. typedef unsigned long long ULL;
  29. typedef pair<int, int> PII;
  30. typedef pair<LD, LD> PDD;
  31. typedef pair<LL, int> PLL;
  32. typedef vector<int> VI;
  33. typedef vector<LL> VLL;
  34. typedef vector<char> VCH;
  35. typedef vector<LD> VLD;
  36. typedef vector<string> VS;
  37. typedef vector<VS> VSS;
  38. typedef vector<VI> VVI;
  39. typedef vector<VLL> VVLL;
  40. typedef vector<VCH> VVCH;
  41. typedef vector<PII> VPII;
  42. typedef vector<PLL> VPLL;
  43. typedef vector<PDD> VPDD;
  44. #define MP make_pair
  45. #define PB push_back
  46. #define X first
  47. #define Y second
  48. #define next fake_next
  49. #define prev fake_prev
  50. #define left fake_left
  51. #define right fake_right
  52.  
  53. #define FOR(i,a,b) for(int i = (a); i < (b); ++i)
  54. #define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); --i)
  55. #define REP(i, t) FOR(i,0,t)
  56. #define ALL(a) a.begin(), a.end()
  57. #define SZ(a) (int)((a).size())
  58. #define FILL(a, value) memset(a, value, sizeof(a))
  59.  
  60. const LD PI = acos(-1.0);
  61. const LD EPS = 1e-4;
  62. const LL INF = 1e7 - 1;
  63. const LL mod = 1000000007;
  64. const LL LINF = 1e18 + 10;
  65. const int MAXN = 100001;
  66. const int MAXK = 101;
  67.  
  68. struct project
  69. {
  70. string nazva;//стрінгова назва
  71. int version;//версія
  72. int cnt;//кількість букв в назві
  73. int index = -1;//індекс - номер цього проекту у вхідних даних
  74. char name[10];//щоб зчитати стрінгову назву
  75. vector<project> G;//проекти від яких залежить
  76.  
  77. void just_this()//просто назва і версія
  78. {
  79. cnt = 0;
  80. char ch;
  81. while (ch = getchar())//поки не ' ' чи '\n'
  82. {
  83. if (ch >= 'a' && ch <= 'z')
  84. name[cnt++] = ch;
  85. else
  86. {
  87. if (cnt)
  88. break;
  89. }
  90. }
  91.  
  92. nazva.clear();
  93. FOR(i, 0, cnt)
  94. nazva += name[i];//мутим назву
  95.  
  96. scanf("%d", &version);
  97. }
  98.  
  99. void read()
  100. {
  101. just_this();
  102. int x;
  103. scanf("%d", &x); //зчитуєм залежності
  104. project pr;
  105. FOR(i, 0, x)
  106. {
  107. pr.just_this();
  108. G.push_back(pr);
  109. }
  110. }
  111. };
  112.  
  113. int N;
  114. project A[MAXN];//всі проекти
  115. int dist[MAXN];//для бфсу
  116. char used[MAXN];//для бфсу
  117. vector<project> ANS;//їбать, що ж це таке?
  118. map<pair<int, string>, int> mp;//мапка проект - його індекс (хуй його знає нашо)
  119. map<string, int> best;//номер проекту, який ми беремо для конкретної назви
  120. VI levels[MAXN];//пошаровий бфс
  121.  
  122. VI solve(VI curr_level)//викидає непотрібні на цьому шарі бфсу
  123. {
  124. map<string, int> ok;
  125. for (auto i : curr_level)
  126. {
  127. if (A[i].nazva == A[0].nazva)
  128. continue;
  129.  
  130. if (best[A[i].nazva])
  131. continue;
  132.  
  133. int now = ok[A[i].nazva];
  134. if (now == 0)
  135. ok[A[i].nazva] = i;
  136. else
  137. {
  138. if (A[now].version < A[i].version)
  139. ok[A[i].nazva] = i;
  140. }
  141. }
  142.  
  143. VI res;
  144. for (auto i : ok)
  145. res.push_back(i.Y), best[i.X] = i.Y;
  146.  
  147. return res;
  148. }
  149.  
  150. void bfs()//складність - О(дохуя)
  151. {
  152. FILL(used, 0);
  153. FILL(dist, 0);
  154. queue<int> q;
  155. q.push(0);
  156. used[0] = 1;
  157. int curr = 1;
  158. VI level;
  159. int iter = 1;
  160. while (!q.empty())
  161. {
  162. while (!q.empty())
  163. {
  164. int t = q.front();
  165. q.pop();
  166. FOR(x, 0, SZ(A[t].G))
  167. {
  168. int i = A[t].G[x].index;
  169. if (used[i] == 0)
  170. level.push_back(i);
  171. }
  172. }
  173.  
  174. if (SZ(level) == 0)//чи вже кінець
  175. continue;
  176.  
  177. level = solve(level);//викидаєм то шо не треба
  178. for (auto i : level)
  179. {
  180. used[i] = 1;
  181. dist[i] = iter;
  182. q.push(i);
  183. }
  184.  
  185. level.clear();
  186. ++iter;
  187. }
  188. }
  189.  
  190. int comp(project x, project y)//лексикографічний сорт стрінгів
  191. {
  192. int mi = min(x.cnt, y.cnt);
  193. FOR(i, 0, mi)
  194. if (x.name[i] > y.name[i])
  195. return 0;
  196. else
  197. if (x.name[i] < y.name[i])
  198. return 1;
  199.  
  200. return x.cnt < y.cnt;
  201. }
  202.  
  203. int main()
  204. {
  205. //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  206. freopen("In.txt", "r", stdin);
  207.  
  208. scanf("%d", &N);
  209. FOR(i, 0, N)
  210. {
  211. A[i].read();
  212. A[i].index = i;
  213. mp[MP(A[i].version, A[i].nazva)] = i;//для того шоб потім знати індекси проектів які ще не зчитали
  214. }
  215.  
  216. FOR(i, 0, N)
  217. {
  218. for (auto& pr : A[i].G)
  219. pr.index = mp[MP(pr.version, pr.nazva)];//власне взнаєм ті індекси
  220. }
  221.  
  222. bfs();//бфс
  223. for (auto i : best)
  224. ANS.push_back(A[i.Y]);
  225.  
  226. sort(ALL(ANS), comp);
  227. cout << SZ(ANS) << endl;
  228. FOR(i, 0, SZ(ANS))
  229. {
  230. FOR(j, 0, ANS[i].cnt)
  231. printf("%c", ANS[i].name[j]);
  232.  
  233. printf(" %d\n", ANS[i].version);
  234. }
  235.  
  236. return 0;
  237. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement