Guest User

Untitled

a guest
Dec 12th, 2014
476
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.69 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8.  
  9. vector <int> v[100010];
  10. vector <pair<int, int> > pos[100010];
  11. int us[100010];
  12.  
  13. bool cmp(pair<int, int> a, pair<int, int> b) {
  14.     if(a.fi == 0)
  15.         return 1;
  16.     if(b.fi == 0)
  17.         return 0;
  18.     return a.fi < b.fi;
  19. }
  20.  
  21. bool dfs(int cur, int g = 1, int l = 0) {
  22.     us[cur] = g;
  23.     int d = 0;
  24.     for(auto x: v[cur]) {
  25. //        cout << cur << ' ' << x << "\n";
  26. //        cout << us[cur] << ' ' << g << '\n';
  27. //        cout << us[x] << ' ' << g % 2 + 1 << "\n\n";
  28.         if(us[x] && us[x] != g % 2 + 1) {
  29.             cout << "-1";
  30.             exit(0);
  31.         } if(!us[x]) {
  32.             d = 1;
  33.             int q = (l >= 0 ? 1: -1);
  34.             if(dfs(x, g % 2 + 1, q)) {
  35.                 if(l == 100) {
  36.                     cout << "-1";
  37.                     exit(0);
  38.                 } else if(l == -1) {
  39.                     pos[cur].pb({-1, x});
  40.                     l = 100;
  41.                 } else {
  42.                     pos[cur].pb({1, x});
  43.                     l = (l == 0 ? -1: 100);
  44.                 }
  45.             } else {
  46.                 pos[cur].pb({0, x});
  47.             }
  48.         }
  49.     }
  50.     sort(pos[cur].begin(), pos[cur].end());
  51.     return d;
  52. }
  53.  
  54. vector <pair<int, int> > l[2];
  55. int mn[2];
  56.  
  57. void dfs1(int cur, int line = 0) {
  58. //    cout << cur << ' ' << line << "\n";
  59.     for(auto x: pos[cur]) {
  60. //        cout << x.fi << ' ' << x.se << '\n';
  61.         if(x.fi == -1) {
  62.             dfs1(x.se, line^1);
  63. //            l[line^1].pb({mn[line^1], x.se});
  64.             mn[line^1]++;
  65.         } else if(x.fi == 0) {
  66.             l[line^1].pb({mn[line^1], x.se});
  67.             mn[line^1]++;
  68.         }
  69.     }
  70. //    cout << "\n";
  71.     l[line].pb({mn[line], cur});
  72.     if(!pos[cur].empty() && pos[cur].back().fi == 1) {
  73. //        l[line^1].pb({mn[line^1], pos[cur].back().se});
  74.         mn[line^1]++;
  75.         dfs1(pos[cur].back().se, line^1);
  76.     }
  77. }
  78.  
  79. int main() {
  80. //    freopen("input.txt", "r", stdin);
  81.     freopen("gods.in", "r", stdin);
  82.     freopen("gods.out", "w", stdout);
  83.  
  84.     int n, i, x, j, y;
  85.     cin >> n;
  86.     for(i = 1; i <= n; i++) {
  87.         cin >> x;
  88.         for(j = 1; j <= x; j++) {
  89.             cin >> y;
  90.             v[i].pb(y);
  91.         }
  92.     }
  93.     for(i = 1; i <= n; i++) {
  94.         if(!us[i]) {
  95.             if(v[i].size() == 1)
  96.                 dfs(v[i][0]), dfs1(v[i][0]);
  97.             else
  98.                 dfs(i), dfs1(i);
  99.         }
  100.     }
  101.     cout << l[0].size() << ' ' << l[1].size() << "\n";
  102.     for(auto x: l[0])
  103.         cout << x.se << " ";
  104.     cout << "\n";
  105.     for(auto x: l[1])
  106.         cout << x.se << " ";
  107.     cout << "\n";
  108. ////
  109. }
Advertisement
Add Comment
Please, Sign In to add comment