daily pastebin goal
4%
SHARE
TWEET

Untitled

a guest Oct 21st, 2018 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top