Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- #define fr first
- #define sc second
- #define pb push_back
- #define pii pair<int, int>
- #define mp make_pair
- const int maxn = 1e5 + 88;
- const int inf = 1e9 + 88;
- const ll infll = 1e18 + 88;
- const ld PI = acos(-1);
- const ld eps = 1e-9;
- const ll mod = 1e9;
- map<pair<string, int>, int> names;
- vector<pair<string, int> > namest;
- map<string, pair<int, int> > zv;
- int nn = 1;
- int n;
- vector<int> gr[maxn];
- bool used[maxn];
- int addpr(string s, int v)
- {
- if (names[{s, v}] == 0)
- {
- names[{s, v}] = nn;
- nn++;
- namest.pb({s, v});
- return nn - 1;
- }
- else
- return names[{s, v}];
- }
- pair<string, int> getv(int v)
- {
- return namest[v - 1];
- }
- string pcp;
- void bfs()
- {
- map<string, pair<int, int> > vr;
- queue<pair<int, int> > q;
- q.push({1, 1});
- while (q.size())
- {
- auto v = q.front();
- q.pop();
- vr.clear();
- for (int tv : gr[v.fr])
- {
- auto ttv = getv(tv);
- if (vr[ttv.fr].fr < ttv.sc)
- {
- vr[ttv.fr] = {ttv.sc, tv};
- }
- }
- for (auto tv : vr)
- {
- if (tv.fr != pcp)
- {
- if (!zv.count(tv.fr) || (zv[tv.fr].sc == v.sc && zv[tv.fr].fr < tv.sc.fr))
- {
- zv[tv.fr] = {tv.sc.fr, v.sc};
- q.push({tv.sc.sc, v.sc + 1});
- }
- }
- }
- }
- }
- void solve()
- {
- cin >> n;
- for (int i = 0; i < n; i++)
- {
- string tn;
- int v;
- cin >> tn >> v;
- if (i == 0)
- pcp = tn;
- int nv = addpr(tn, v);
- int tc;
- cin >> tc;
- for (int j = 0; j < tc; j++)
- {
- cin >> tn >> v;
- gr[nv].pb(addpr(tn, v));
- }
- }
- bfs();
- cout << zv.size() << endl;
- vector<pair<string, int> > tt;
- for (auto t : zv)
- {
- tt.pb({t.fr, t.sc.fr});
- }
- sort(tt.begin(), tt.end());
- for (int i = 0; i < tt.size(); i++)
- cout << tt[i].fr << " " << tt[i].sc << "\n";
- }
- /*struct bornode
- {
- int per[26];
- };
- vector<bornode> bor;
- int borcount(const string &p)
- {
- int nn = 0;
- for (int i = 0; i < p.size(); i++)
- {
- if (bor[nn].per[p[i] - 'a'] == -1)
- return 0;
- else
- nn = bor[nn].per[p[i] - 'a'];
- }
- for (int i = 0; i < 26; i++)
- if (bor[nn].per[i] != -1)
- return 2;
- return 1;
- }
- bornode getnewbornode()
- {
- bornode t;
- for (int i = 0; i < 26; i++)
- t.per[i] = -1;
- return t;
- }
- void addbor(const string &s)
- {
- int nn = 0;
- for (int i = 0; i < s.size(); i++)
- {
- if (bor[nn].per[s[i] - 'a'] != -1)
- nn = bor[nn].per[s[i] - 'a'];
- else
- {
- bor.pb(getnewbornode());
- bor[nn].per[s[i] - 'a'] = bor.size() - 1;
- nn = bor.size() - 1;
- }
- }
- }
- string prep = ".,?!'- \n";
- bool isprep(char c)
- {
- for (int i = 0; i < prep.size(); i++)
- if (prep[i] == c)
- return 1;
- return 0;
- }
- void solve()
- {
- bor.pb(getnewbornode());
- string s;
- int ans = 0;
- char c;
- int st = 0;
- string w = "";
- while (cin.get(c))
- {
- case 0:
- if (isprep(c))
- {
- ans++;
- }
- else
- {
- w += c;
- st = 1;
- /*if (borcount(w) == 1)
- {
- ans++;
- ans++;
- }
- else
- {
- ans += w.size();
- }
- addbor(w);
- }
- break;
- case 1:
- break;
- }
- cout << ans << endl;
- }*/
- int main()
- {
- freopen("input.txt", "r", stdin);
- srand(time(NULL));
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement