Advertisement
Guest User

Untitled

a guest
May 23rd, 2018
188
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.36 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <set>
  3. #include <map>
  4. #include <deque>
  5. #include <cmath>
  6. #include <queue>
  7. #include <time.h>
  8. #include <string>
  9. #include <cstdio>
  10. #include <vector>
  11. #include <cstdlib>
  12. #include <iostream>
  13. #include <algorithm>
  14. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  15. #define endl '\n'
  16. #define po pop_back()
  17. #define pbc push_back
  18. #define queuel queue<long long>
  19. #define all(x) x.begin(),x.end()
  20. #define matrix vector<vector<ll>>
  21. #define pin(p) cin >> p.first >> p.second;
  22. #define rev(v) reverse(v.begin(),v.end());
  23. #define mx(v) max_element(v.begin(), v.end());
  24. #define mn(v) min_element(v.begin(), v.end());
  25. #define pout(p) cout << p.first << " " << p.second;
  26. #define er(v, l, r) erase(v.begin() + l, v.begin() + r);
  27. #define vin(v) for(int i = 0; i < v.size(); ++i) cin >> v[i];
  28. #define vout(v,c) for(int i = 0; i < v.size(); ++i) cout << v[i]<<c;
  29. #define push(v, a) for(int i = 0; i < a.size(); ++i) v.push_back(a[i]);
  30. #define fastio() ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);srand(time(NULL));
  31. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  32. using namespace std;
  33. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  34. typedef long long ll;
  35. typedef long double ld;
  36. typedef unsigned long long ull;
  37. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  38. const ll INF = 1000LL * 1000 * 1000 * 1000 * 1000 * 1000;
  39. const int inf = 1000 * 1000 * 1000;
  40. const ld PI = acos(-1.0);
  41. const int mod = inf + 7;
  42. const ld EPS = 1e-9;
  43. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  44. vector<string> noocean{ "Mongolia", "Nepal", "Bhutan", "Laos","Kyrgyzstan", "Afghanistan","Tajikistan", "Jordan", "Armenia", "Uzbekistan","Kazakhstan","Turkmenistan","Azerbaijan" };
  45. int main()
  46. {
  47. fastio();
  48. freopen("Probabilities.txt", "r", stdin);
  49. double mx = 0;
  50. vector<pair<string, double>> sts;
  51. map<string, double> vari;
  52. for (int i = 0; i < 45; ++i)
  53. {
  54. string s;
  55. cin >> s;
  56. double a;
  57. cin >> a;
  58. mx = max(mx, a);
  59. sts.pbc({ s,a });
  60. vari[s] = a;
  61. }
  62. map<string, vector<string>> g;
  63. g["Nepal"].pbc("China");
  64. g["Nepal"].pbc("India");
  65. g["India"].pbc("Nepal");
  66. g["China"].pbc("Nepal");
  67. g["India"].pbc("Bangladesh");
  68. g["Bangladesh"].pbc("India");
  69. g["India"].pbc("Myanmar");
  70. g["Myanmar"].pbc("India");
  71. g["Bangladesh"].pbc("Myanmar");
  72. g["Myanmar"].pbc("Bangladesh");
  73. g["Kuwait"].pbc("Iraq");
  74. g["Iraq"].pbc("Kuwait");
  75. g["Malaysia"].pbc("Thailand");
  76. g["Indonesia"].pbc("Malaysia");
  77. g["Thailand"].pbc("Malaysia");
  78. g["Malaysia"].pbc("Indonesia");
  79. g["Cambodja"].pbc("Thailand");
  80. g["Thailand"].pbc("Cambodja");
  81. g["Vietnam"].pbc("Cambodja");
  82. g["Cambodja"].pbc("Vietnam");
  83. g["Vietnam"].pbc("China");
  84. g["China"].pbc("Vietnam");
  85. g["Singapore"].pbc("Malaysia");
  86. g["Malaysia"].pbc("Singapore");
  87. g["Korea"].pbc("DPRK");
  88. g["DPRK"].pbc("Korea");
  89. g["China"].pbc("Mongolia");
  90. g["Mongolia"].pbc("China");
  91. g["China"].pbc("DPRK");
  92. g["DPRK"].pbc("China");
  93. g["Laos"].pbc("Vietnam");
  94. g["Vietnam"].pbc("Laos");
  95. g["Cambodja"].pbc("Laos");
  96. g["Laos"].pbc("Cambodja");
  97. g["Laos"].pbc("Thailand");
  98. g["Thailand"].pbc("Laos");
  99. g["Laos"].pbc("Myanmar");
  100. g["Myanmar"].pbc("Laos");
  101. g["Bhutan"].pbc("China");
  102. g["China"].pbc("Bhutan");
  103. g["Bhutan"].pbc("India");
  104. g["India"].pbc("Bhutan");
  105. g["Afghanistan"].pbc("China");
  106. g["China"].pbc("Afghanistan");
  107. g["Pakistan"].pbc("India");
  108. g["Pakistan"].pbc("Iran");
  109. g["Pakistan"].pbc("Afghanistan");
  110. g["India"].pbc("Pakistan");
  111. g["Iran"].pbc("Pakistan");
  112. g["Afghanistan"].pbc("Pakistan");
  113. g["China"].pbc("Kazakhstan");
  114. g["Kazakhstan"].pbc("China");
  115. g["Mongolia"].pbc("Kazakhstan");
  116. g["Kazakhstan"].pbc("Mongolia");
  117. g["Kazakhstan"].pbc("Uzbekistan");
  118. g["Uzbekistan"].pbc("Kazakhstan");
  119. g["Yemen"].pbc("Oman");
  120. g["Oman"].pbc("Yemen");
  121. g["Saudi-Arabia"].pbc("Yemen");
  122. g["Yemen"].pbc("Saudi-Arabia");
  123. g["Oman"].pbc("United-Arab-Emirates");
  124. g["United-Arab-Emirates"].pbc("Oman");
  125. g["Oman"].pbc("Saudi-Arabia");
  126. g["Saudi-Arabia"].pbc("Oman");
  127. g["United-Arab-Emirates"].pbc("Saudi-Arabia");
  128. g["Saudi-Arabia"].pbc("United-Arab-Emirates");
  129. g["Saudi-Arabia"].pbc("Qatar");
  130. g["Qatar"].pbc("Saudi-Arabia");
  131. g["Kuwait"].pbc("Iraq");
  132. g["Kuwait"].pbc("Saudi-Arabia");
  133. g["Saudi-Arabia"].pbc("Kuwait");
  134. g["Iraq"].pbc("Kuwait");
  135. g["Tajikistan"].pbc("Uzbekistan");
  136. g["Uzbekistan"].pbc("Tajikistan");
  137. g["Turkmenistan"].pbc("Uzbekistan");
  138. g["Uzbekistan"].pbc("Turkmenistan");
  139. g["Kazakhstan"].pbc("Turkmenistan");
  140. g["Turkmenistan"].pbc("Kazakhstan");
  141. g["Turkmenistan"].pbc("Iran");
  142. g["Iran"].pbc("Turkmenistan");
  143. g["Iraq"].pbc("Iran");
  144. g["Iran"].pbc("Iraq");
  145. g["Kyrgyzstan"].pbc("China");
  146. g["Kyrgyzstan"].pbc("Kazakhstan");
  147. g["Kyrgyzstan"].pbc("Uzbekistan");
  148. g["Kyrgyzstan"].pbc("Tajikistan");
  149. g["China"].pbc("Kyrgyzstan");
  150. g["Kazakhstan"].pbc("Kyrgyzstan");
  151. g["Uzbekistan"].pbc("Kyrgyzstan");
  152. g["Tajikistan"].pbc("Kyrgyzstan");
  153. g["Georgia"].pbc("Turkey");
  154. g["Turkey"].pbc("Georgia");
  155. g["Georgia"].pbc("Armenia");
  156. g["Armenia"].pbc("Georgia");
  157. g["Georgia"].pbc("Azerbaijan");
  158. g["Azerbaijan"].pbc("Georgia");
  159. g["Armenia"].pbc("Azerbaijan");
  160. g["Azerbaijan"].pbc("Armenia");
  161. g["Azerbaijan"].pbc("Turkey");
  162. g["Turkey"].pbc("Azerbaijan");
  163. g["Syria"].pbc("Lebanon");
  164. g["Lebanon"].pbc("Syria");
  165. g["Syria"].pbc("Turkey");
  166. g["Turkey"].pbc("Syria");
  167. g["Syria"].pbc("Jordan");
  168. g["Jordan"].pbc("Syria");
  169. g["Syria"].pbc("Israel");
  170. g["Israel"].pbc("Syria");
  171. g["Palestine"].pbc("Israel");
  172. g["Israel"].pbc("Palestine");
  173. g["Azerbaijan"].pbc("Iran");
  174. g["Iran"].pbc("Azerbaijan");
  175. g["Armenia"].pbc("Iran");
  176. g["Iran"].pbc("Armenia");
  177. g["Lebanon"].pbc("Israel");
  178. g["Israel"].pbc("Lebanon");
  179. g["Lebanon"].pbc("Jordan");
  180. g["Jordan"].pbc("Lebanon");
  181.  
  182. for (auto i : vari)
  183. {
  184. if (find(noocean.begin(), noocean.end(), i.first) != noocean.end())
  185. {
  186. continue;
  187. }
  188. g["Ocean"].pbc(i.first);
  189. g[i.first].pbc("Ocean");
  190. }
  191. vari["Ocean"] = 0.447;
  192. for (auto i : vari)
  193. {
  194. if (i.first == "Ocean")
  195. {
  196. continue;
  197. }
  198. string s = i.first;
  199. map<string, double> d;
  200. for (auto j : vari)
  201. {
  202. d[j.first] = 42.9999;
  203. }
  204. d[s] = 0;
  205. set<pair<double, string>> q;
  206. q.insert({ d[s],s });
  207. while (!q.empty())
  208. {
  209. string v = q.begin()->second;
  210. q.erase(q.begin());
  211. for (int j = 0; j < g[v].size(); ++j)
  212. {
  213. string to = g[v][j];
  214. double len = 1 - (1 - d[v])*(1 - vari[to]);
  215. if (len < d[to])
  216. {
  217. q.erase({ d[to],to });
  218. d[to] = len;
  219. q.insert({ d[to],to });
  220. }
  221. }
  222. }
  223. double maxd = 0;
  224. for (auto j : d)
  225. {
  226. if (j.first == "Ocean")
  227. {
  228. continue;
  229. }
  230. maxd = max(maxd, j.second);
  231. }
  232. if (maxd<=0.5)
  233. {
  234. cout << i.first << endl;
  235. }
  236. }while (1);
  237. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement