Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ALL(x) x.begin(), x.end()
- #define pb push_back
- #define ld long double
- typedef unsigned long long int lli;
- using namespace std;
- const lli INF =1e9+ 7;
- const int N =1000;
- pair< string, int> nodes[N+100];
- vector< vector< int > > g;
- vector< bool > us(N);
- map< string, int > ans;
- map< string, int > iter[N+100];
- map<string, vector< int > > pro;
- map< string , bool > pro_us;
- void bad_dfs( int x){
- us[x] =1;
- for(auto it: g[x]){
- if(!us[it]) bad_dfs(it);
- }
- }
- void try_add(int x, int i){
- string s= nodes[x].first;
- if(!iter[i].count(s)){
- iter[i][s] =x;
- }
- else {
- int v =iter[i][s];
- if(nodes[v].second < nodes[x].second){
- iter[i][s]= x;
- }
- }
- }
- void dfs( int x){
- iter[0][nodes[x].first] = x;
- for(int i(0); i<N+5; i++){
- for(auto it:iter[i]){
- if(us[it.second] )continue;
- ans[it.first] = it.second;
- for(auto jt: g[it.second]){
- if( !us[jt]) try_add(jt, i+1);
- }
- }
- for(auto it:iter[i+1]){
- if(!pro_us[it.first]){
- pro_us[it.first] = 1;
- for( auto kt: pro[it.first]){
- if(!us[kt] && kt != it.second ) bad_dfs(kt);
- }
- }
- }
- }
- }
- int main(){
- freopen("in.txt", "r", stdin);
- int n;
- scanf("%d",&n);
- g.resize(n);
- vector< vector< pair< string , int > > > z(n);
- map< pair< string, int > , int > mt;
- for( int i(0); i<n; i++){
- cin>>nodes[i].first>> nodes[i].second;
- mt[nodes[i]] = i;
- pro[nodes[i].first].pb(i);
- int k;
- scanf("%d",&k);
- for( int j(0); j<k; j++){
- pair<string, int >tmp;
- cin>>tmp.first>>tmp.second;
- z[i].pb(tmp);
- }
- }
- for( int i(0); i<n; i++){
- for( int j(0); j<z[i].size(); j++){
- g[i].pb(mt[z[i][j]]);
- }
- }
- for( int i(0); i<n; i++) pro_us[nodes[i].first] = 0;
- for(auto it: pro[nodes[0].first]) if(it != 0) bad_dfs(it);
- dfs(0);
- if(ans.count(nodes[0].first)){
- auto it = ans.find(nodes[0].first);
- ans.erase(it);
- }
- printf("%d\n",ans.size());
- for(auto it:ans){
- cout<< it.first<<" "<<nodes[it.second].second<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement