sacgajcvs

sol

Apr 11th, 2020
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.36 KB | None | 0 0
  1. /*
  2.  
  3. 1
  4. 8
  5. ID4 Name4 Address4
  6. ID3 Name3 Address3
  7. ID2 Name2 Address2
  8. ID1 Name1 Address1
  9. ID5 Name5 Address5
  10. ID7 Name7 Address7
  11. ID6 Name6 Address6
  12. ID8 Name8 Address8
  13. ID4 2 ID3 ID7
  14. ID3 3 ID4 ID7 ID5
  15. ID2 1 ID8
  16. ID1 3 ID6 ID8 ID2
  17. ID5 2 ID3 ID7
  18. ID7 3 ID4 ID3 ID5
  19. ID6 1 ID1
  20. ID8 2 ID2 ID1
  21. 3
  22. ID2
  23. ID4
  24. ID3
  25.  
  26. _____ _ _ _ _
  27. |_ _| |__ ___ / \ _ __ ___| |__ _ _| |
  28. | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  29. | | | | | | __// ___ \| | | \__ \ | | | |_| | |
  30. |_| |_| |_|\___/_/ \_\_| |_|___/_| |_|\__,_|_|
  31.  
  32. */
  33. #include<bits/stdc++.h>
  34. #include <ext/pb_ds/assoc_container.hpp>
  35. #include <ext/pb_ds/tree_policy.hpp>
  36. #define ll long long
  37. #define pb push_back
  38. #define ppb pop_back
  39. #define endl '\n'
  40. #define mii map<ll,ll>
  41. #define msi map<string,ll>
  42. #define mis map<ll, string>
  43. #define rep(i,a,b) for(ll i=a;i<b;i++)
  44. #define repr(i,a,b) for(ll i=b-1;i>=a;i--)
  45. #define trav(a, x) for(auto& a : x)
  46. #define pii pair<ll,ll>
  47. #define vi vector<ll>
  48. #define vii vector<pair<ll, ll>>
  49. #define vs vector<string>
  50. #define all(a) (a).begin(),(a).end()
  51. #define F first
  52. #define S second
  53. #define sz(x) (ll)x.size()
  54. #define hell 1000000007
  55. #define lbnd lower_bound
  56. #define ubnd upper_bound
  57. #define max(a,b) (a>b?a:b)
  58. #define min(a,b) (a<b?a:b)
  59.  
  60. /* For Debugging */
  61. #define DEBUG cerr<<"\n>>>I'm Here<<<\n"<<endl;
  62. #define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
  63. #define what_is(x) cerr << #x << " is " << x << endl;
  64.  
  65. std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
  66. #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
  67. #define TIME cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
  68. #define DECIMAL(n) cout << fixed ; cout << setprecision(n);
  69. #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  70. using namespace __gnu_pbds;
  71. using namespace std;
  72. #define PI 3.141592653589793
  73. #define N 100005
  74. /*
  75. Instructions :
  76. 1. Set p each i of p eqaul to i initailly.
  77. 2. rank is initiialised with 0.
  78. 3. To know parent run a loop for each value call find function.
  79. */
  80. ll high[N];
  81. ll p[N]; // set p of i equal to i initially
  82. ll find(ll x)
  83. {
  84. if(p[x]!=x)
  85. p[x]=find(p[x]);
  86. return p[x];
  87. }
  88. void merge(ll x,ll y)
  89. {
  90. ll Px,Py;
  91. Px=find(x);
  92. Py=find(y);
  93. if(high[Px]>high[Py])
  94. p[Py]=Px;
  95. else
  96. p[Px]=Py;
  97. if(high[Px]==high[Py])
  98. high[Py]++;
  99. }
  100. void solve()
  101. {
  102. ll n;
  103. cin>>n;
  104. string id,name,address;
  105. vector<vector<string>> v(n,vector<string>(3));
  106. map<string,ll> ma;
  107. rep(i,0,n)
  108. {
  109. cin>>v[i][0]>>v[i][1]>>v[i][2];
  110. ma[v[i][0]]=i;
  111. }
  112. rep(i,0,n)
  113. p[i]=i;
  114.  
  115. string s;
  116. ll num1,k,num2;
  117. rep(i,0,n)
  118. {
  119. cin>>s;
  120. num1=ma[s];
  121. cin>>k;
  122. rep(i,0,k)
  123. {
  124. cin>>s;
  125. num2=ma[s];
  126. merge(num1,num2);
  127. }
  128. }
  129. vector<bool> vis(n,0);
  130. vector<string> out;
  131. cin>>k;
  132. rep(i,0,k)
  133. {
  134. cin>>s;
  135. vis[find(ma[s])]=1;
  136. }
  137. rep(i,0,n)
  138. {
  139. if(vis[find(i)])
  140. out.pb(v[i][0]);
  141. }
  142. sort(all(out));
  143. trav(i,out)
  144. {
  145. num1=ma[i];
  146. cout<<v[num1][0]<<" "<<v[num1][1]<<" "<<v[num1][2]<<endl;
  147. }
  148.  
  149. return;
  150. }
  151. int main()
  152. {
  153. #ifndef ONLINE_JUDGE
  154. freopen ("input.txt","r",stdin);
  155. // freopen("output.txt","w",stdout);
  156. #endif
  157. FAST
  158. int TESTS=1;
  159. cin>>TESTS;
  160. while(TESTS--)
  161. {
  162. solve();
  163. }
  164. TIME
  165. return 0;
  166. }
Advertisement
Add Comment
Please, Sign In to add comment