Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.50 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <map>
  5. #include <set>
  6. #include <cmath>
  7. #include <string>
  8. #include <algorithm>
  9. #include <iomanip>
  10. #include <deque>
  11. #include <functional>
  12. typedef long long ll;
  13. typedef long double ld;
  14. const int N = int(1e6) + 7;
  15. const ll INF = ll(1e18) + 111;
  16. const double EPS = 1e-8;
  17. #define pb push_back
  18. #define all(v) v.begin(), v.end()
  19. #define sz(v) v.size()
  20. using namespace std;
  21. template<typename T> inline istream &operator>> (istream &in, vector<T> &v) { for (auto &i : v) { in >> i; } return in; }
  22. template<typename T> inline ostream &operator<< (ostream &out, const vector<T> &v) { if (v.empty()) { return out; } out << v.front(); for (auto it = ++v.begin(); it != v.end(); ++it) { out << ' ' << *it; } return out; }
  23. struct project {
  24. string s;
  25. string name;
  26. int num;
  27. };
  28. struct bfsproject {
  29. int d;
  30. project p;
  31. };
  32. bool operator<(bfsproject a, bfsproject b) {
  33. return a.d < b.d || a.d == b.d && (a.p.num > b.p.num || a.p.name < b.p.name && a.p.num==b.p.num);
  34. }
  35. bool operator!=(project a, project b) {
  36. return a.s != b.s;
  37. }
  38. bool operator<(project a, project b) {
  39. return a.s < b.s;
  40. }
  41. bool comp1(project a, project b) {
  42. return a.name < b.name || a.name==b.name && a.num > b.num;
  43. }
  44. map<project, vector<project>> mp;
  45. map<string, int> used;
  46. vector<vector<project>> a(1005);
  47. vector<project> ans;
  48.  
  49. void bfs(project start) {
  50. set<bfsproject> q;
  51. q.insert({0, start});
  52. while (!q.empty()){
  53. bfsproject v = *q.begin();
  54. q.erase(q.begin());
  55. if (used[v.p.name] == 1) continue;
  56. if (v.p!=start)
  57. ans.push_back(v.p);
  58. used[v.p.name] = 1;
  59. for (project u : mp[v.p]) {
  60. q.insert({v.d + 1,u});
  61. }
  62. }
  63.  
  64. }
  65. int main() {
  66. //ifstream cin("input.txt");
  67. //ofstream cout("output.txt");
  68. int n, buf, k;
  69. cin >> n;
  70. project root;
  71. cin >> root.name >> root.num;
  72. root.s = root.name + to_string(root.num);
  73. cin >> k;
  74. for (int i = 0; i < k; i++) {
  75. project s;
  76. cin >> s.name >> s.num;
  77. s.s = s.name + to_string(s.num);
  78. mp[root].pb(s);
  79. }
  80. for (int i = 0; i < n - 1; i++) {
  81. project t;
  82. cin >> t.name >> t.num;
  83. t.s = t.name + to_string(t.num);
  84. cin >> k;
  85. for (int j = 0; j < k; j++) {
  86. project s;
  87. cin >> s.name >> s.num;
  88. s.s = s.name + to_string(s.num);
  89. mp[t].pb(s);
  90. }
  91. }
  92. bfs(root);
  93.  
  94. for (int i = 1; i < n; i++) {
  95. for (project p : a[i]) {
  96. ans.pb(p);
  97. }
  98. }
  99. sort(all(ans), comp1);
  100. cout << sz(ans) << endl;
  101. for (auto el : ans) {
  102. cout << el.name << " " << el.num << endl;
  103. }
  104. }
  105. close
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement