Advertisement
Guest User

Untitled

a guest
Oct 21st, 2018
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.12 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void doRoutine() {
  5. ios_base::sync_with_stdio(false);
  6. cin.tie(0);
  7. cout.tie(0);
  8. srand(322179);
  9. #ifdef LOCAL
  10. freopen("input.txt", "rt", stdin);
  11. freopen("output.txt", "wt", stdout);
  12. #endif
  13. }
  14.  
  15. #define DBG(VAR) cerr << #VAR << ": " << VAR << endl
  16.  
  17. #define all(x) x.begin(), x.end()
  18. #define vb vector<bool>
  19. #define vi vector<int>
  20. #define vvi vector<vi>
  21. #define pii pair<int, int>
  22. #define fi first
  23. #define se second
  24. #define pb push_back
  25. #define vc vector
  26. #define $ make_pair
  27.  
  28. #ifndef LOCAL
  29. #define cerr if(0) cerr
  30. #define DBG(...) (true)
  31. #endif
  32.  
  33. #define D double
  34. //#define int long long
  35.  
  36. typedef long long ll;
  37.  
  38.  
  39. // ----------------------------- CODE NOW ------------------------
  40.  
  41. template <typename T1, typename T2>
  42. istream & operator >> (istream & in, pair <T1, T2> & p) {
  43. in >> p.fi >> p.se;
  44. return in;
  45. }
  46.  
  47. template <typename T1, typename T2>
  48. ostream & operator << (ostream & out, pair <T1, T2> p) {
  49. out << "{" << p.fi << ", " << p.se << "}";
  50. return out;
  51. }
  52.  
  53. template <typename T>
  54. ostream & operator << (ostream & out, vector <T> arr) {
  55. for (int i = 0; i < arr.size(); ++i)
  56. out << arr[i] << " ";
  57. out << endl;
  58. return out;
  59. }
  60.  
  61. template <typename T>
  62. istream & operator >> (istream & in, vector <T> & arr) {
  63. for (int i = 0; i < arr.size(); ++i)
  64. in >> arr[i];
  65. return in;
  66. }
  67.  
  68. vector <vector <int> > g;
  69.  
  70. vector <int> color;
  71.  
  72. void dfs(int v, int clr) {
  73. color[v] = clr;
  74. for (int i = 0; i < g[v].size(); ++i) {
  75. int to = g[v][i];
  76. if (color[to] == 0)
  77. dfs(to, (clr % 2 ? clr + 1 : clr - 1));
  78. }
  79. }
  80.  
  81. signed main() {
  82. doRoutine();
  83.  
  84. int n;
  85. cin >> n;
  86. g.resize(n);
  87. vector <string> plc(n);
  88. vector <vector <int> > arr(n);
  89. for (int i = 0; i < n; ++i) {
  90. string s;
  91. cin >> s;
  92. plc[i] = s;
  93. int sz;
  94. cin >> sz;
  95. arr[i].resize(sz);
  96. cin >> arr[i];
  97. for (int j = 0; j < arr[i].size(); ++j)
  98. arr[i][j]--;
  99. }
  100.  
  101.  
  102.  
  103. for (int i = 0; i < n; ++i) {
  104. for (auto x : arr[i]) {
  105. if (plc[x] != plc[i]) {
  106. g[x].push_back(i);
  107. g[i].push_back(x);
  108. }
  109. }
  110. }
  111.  
  112. set <int> bb;
  113. for (int i = 0; i < n; ++i) {
  114. set <int> ss;
  115. for (auto x : arr[i])
  116. ss.insert(x);
  117. for (int j = 0; j < n; ++j) {
  118. if (plc[j] == plc[i])
  119. continue;
  120. for (auto x : arr[j])
  121. {
  122. if (plc[x] != plc[j] && plc[x] != plc[i] && ss.count(x)) {
  123. bb.insert(i);
  124. bb.insert(j);
  125. }
  126. }
  127. }
  128. }
  129. for (auto x : bb)
  130. cerr << x << endl;
  131. vector <int> ansall(10000);
  132.  
  133. for (int i = 0; i < n; ++i) {
  134. color.assign(n, 0);
  135. set <int> ban = bb;
  136. vector <int> ans;
  137. if (plc[i] == "pool") {
  138. ban.insert(i);
  139. for (int j = 0; j < n; ++j) {
  140. for (auto x : arr[j]) {
  141. if (x == i && plc[j] != "pool") {
  142. ans.resize(10000);
  143. }
  144. }
  145. }
  146. }
  147. else {
  148. ban.insert(i);
  149. for (int j = 0; j < n; ++j) {
  150. for (auto x : arr[j]) {
  151. if (x == i && plc[j] != "pool") {
  152. if (plc[j] != plc[i])
  153. arr.resize(10001);
  154. else
  155. ban.insert(j);
  156. }
  157. }
  158. }
  159. }
  160.  
  161. int cl = 1;
  162.  
  163. for (int i = 0; i < n; ++i) {
  164. if (color[i] == 0) {
  165. dfs(i, cl);
  166. set <int> a, b;
  167. bool flag1 = false, flag2 = false;
  168. for (int i = 0; i < n; ++i) {
  169. if (color[i] == cl) {
  170. a.insert(i);
  171. if (ban.count(i))
  172. flag1 = true;
  173. }
  174. else if (color[i] == cl + 1) {
  175. b.insert(i);
  176. if (ban.count(i))
  177. flag2 = true;
  178. }
  179. }
  180. if (a.size() > b.size()) {
  181. swap(a, b);
  182. swap(flag1, flag2);
  183. }
  184. if (flag1 && flag2) {
  185. ans.resize(10001);
  186. break;
  187. }
  188. else if (flag2) {
  189. for (auto x : b)
  190. ans.push_back(x);
  191. }
  192. else {
  193. for (auto x : a)
  194. ans.push_back(x);
  195. }
  196. cl += 2;
  197. }
  198. }
  199. if (ans.size() < ansall.size())
  200. ansall = ans;
  201. }
  202. assert(ansall.size() <= n);
  203. cout << ansall.size() << endl;
  204. for (auto & x : ansall)
  205. x++;
  206. cout << ansall << endl;
  207. return 0;
  208. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement