Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <map>
- #include <set>
- #include <cmath>
- #include <string>
- #include <algorithm>
- #include <iomanip>
- #include <deque>
- #include <functional>
- typedef long long ll;
- typedef long double ld;
- const int N = int(1e6) + 7;
- const ll INF = ll(1e18) + 111;
- const double EPS = 1e-8;
- #define pb push_back
- #define all(v) v.begin(), v.end()
- #define sz(v) v.size()
- using namespace std;
- template<typename T> inline istream &operator>> (istream &in, vector<T> &v) { for (auto &i : v) { in >> i; } return in; }
- 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; }
- struct project {
- string s;
- string name;
- int num;
- };
- struct bfsproject {
- int d;
- project p;
- };
- bool operator<(bfsproject a, bfsproject b) {
- 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);
- }
- bool operator!=(project a, project b) {
- return a.s != b.s;
- }
- bool operator<(project a, project b) {
- return a.s < b.s;
- }
- bool comp1(project a, project b) {
- return a.name < b.name || a.name==b.name && a.num > b.num;
- }
- map<project, vector<project>> mp;
- map<string, int> used;
- vector<vector<project>> a(1005);
- vector<project> ans;
- void bfs(project start) {
- set<bfsproject> q;
- q.insert({0, start});
- while (!q.empty()){
- bfsproject v = *q.begin();
- q.erase(q.begin());
- if (used[v.p.name] == 1) continue;
- if (v.p!=start)
- ans.push_back(v.p);
- used[v.p.name] = 1;
- for (project u : mp[v.p]) {
- q.insert({v.d + 1,u});
- }
- }
- }
- int main() {
- //ifstream cin("input.txt");
- //ofstream cout("output.txt");
- int n, buf, k;
- cin >> n;
- project root;
- cin >> root.name >> root.num;
- root.s = root.name + to_string(root.num);
- cin >> k;
- for (int i = 0; i < k; i++) {
- project s;
- cin >> s.name >> s.num;
- s.s = s.name + to_string(s.num);
- mp[root].pb(s);
- }
- for (int i = 0; i < n - 1; i++) {
- project t;
- cin >> t.name >> t.num;
- t.s = t.name + to_string(t.num);
- cin >> k;
- for (int j = 0; j < k; j++) {
- project s;
- cin >> s.name >> s.num;
- s.s = s.name + to_string(s.num);
- mp[t].pb(s);
- }
- }
- bfs(root);
- for (int i = 1; i < n; i++) {
- for (project p : a[i]) {
- ans.pb(p);
- }
- }
- sort(all(ans), comp1);
- cout << sz(ans) << endl;
- for (auto el : ans) {
- cout << el.name << " " << el.num << endl;
- }
- }
- close
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement