Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <cstdio>
- #include <vector>
- #include <string>
- #include <iostream>
- #include <algorithm>
- #include <map>
- #include <iterator>
- #include <functional>
- #include <set>
- #include <stack>
- #include <queue>
- #include <deque>
- #include <fstream>
- #include <iomanip>
- #include <numeric>
- #include <cmath>
- #include <list>
- #include <sstream>
- #include <cstring>
- #include <stdio.h>
- using namespace std;
- #pragma GCC optimize("O3")
- #pragma GCC target("sse4")
- typedef long double LD;
- typedef long long LL;
- typedef unsigned long long ULL;
- typedef pair<int, int> PII;
- typedef pair<LD, LD> PDD;
- typedef pair<LL, int> PLL;
- typedef vector<int> VI;
- typedef vector<LL> VLL;
- typedef vector<char> VCH;
- typedef vector<LD> VLD;
- typedef vector<string> VS;
- typedef vector<VS> VSS;
- typedef vector<VI> VVI;
- typedef vector<VLL> VVLL;
- typedef vector<VCH> VVCH;
- typedef vector<PII> VPII;
- typedef vector<PLL> VPLL;
- typedef vector<PDD> VPDD;
- #define MP make_pair
- #define PB push_back
- #define X first
- #define Y second
- #define next fake_next
- #define prev fake_prev
- #define left fake_left
- #define right fake_right
- #define FOR(i,a,b) for(int i = (a); i < (b); ++i)
- #define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); --i)
- #define REP(i, t) FOR(i,0,t)
- #define ALL(a) a.begin(), a.end()
- #define SZ(a) (int)((a).size())
- #define FILL(a, value) memset(a, value, sizeof(a))
- const LD PI = acos(-1.0);
- const LD EPS = 1e-4;
- const LL INF = 1e7 - 1;
- const LL mod = 1000000007;
- const LL LINF = 1e18 + 10;
- const int MAXN = 10001;
- const int MAXK = 101;
- int compar(string x, string y)
- {
- int mi = min(SZ(x), SZ(y));
- FOR(i, 0, mi)
- if (x[i] > y[i])
- return 0;
- else
- if (x[i] < y[i])
- return 1;
- return SZ(x) < SZ(y);
- }
- struct project
- {
- string name;
- int version;
- int index;
- VI sons;
- vector<project> children;
- };
- bool operator<(const project& p, const project& r)
- {
- return compar(p.name, r.name);
- }
- int n;
- vector<project> a;
- map<pair<string, int>, int> mp;
- map<string, vector<project>> names;
- VCH used;
- VI dist;
- vector<string> ans;
- vector<project> res;
- void bfs()
- {
- queue<int> q;
- q.push(0);
- used.assign(n, 0);
- dist.assign(n, 0);
- used[0] = 1;
- while (!q.empty())
- {
- int t = q.front();
- q.pop();
- for(auto i: a[t].sons)
- if (used[i] == 0)
- {
- used[i] = 1;
- dist[i] = 1 + dist[t];
- q.push(i);
- }
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
- //freopen("In.txt", "r", stdin);
- a.clear();
- cin >> n;
- string suka;
- FOR(i, 0, n)
- {
- //в рот їбав ссаний ввід
- //хуй його зна скільки вже пишу, а воно видає хуйню їбану якусь
- }
- FOR(i, 0, n)
- {
- for (auto j : a[i].children)
- {
- auto wtf = MP(j.name, j.version);
- a[i].sons.push_back(mp[wtf]);
- }
- }
- FOR(i, 0, n)
- names[a[i].name].push_back(a[i]);
- bfs();
- cout << SZ(names) << endl;
- for (map<string, vector<project>>::iterator it = names.begin(); it != names.end(); ++it)
- {
- auto i = *it;
- auto vec = i.Y;
- for(auto j: vec)
- if (used[j.index] == 1)
- {
- ans.push_back(i.X);
- break;
- }
- }
- for (auto i : ans)
- {
- auto vec = names[i];
- project best;
- for(auto j: vec)
- if (used[j.index])
- {
- best = j;
- break;
- }
- for(auto j: vec)
- if (used[j.index])
- {
- if (dist[j.index] < dist[best.index])
- best = j;
- else
- {
- if (dist[j.index] == dist[best.index])
- {
- if (j.version > best.version)
- best = j;
- }
- }
- }
- res.push_back(best);
- }
- cout << SZ(res) << endl;
- sort(ALL(res));
- for (auto i : res)
- cout << i.name << " " << i.version << endl;
- cin >> n;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement