peltorator

!2-SAT (doesn't work)

Jan 23rd, 2018
66
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <map>
  5. #include <algorithm>
  6. #include <math.h>
  7. #include <string>
  8. #include <cstring>
  9. #include <set>
  10. using namespace std;
  11.  
  12. typedef long long ll;
  13. typedef double ld;
  14.  
  15. const int N = 2000003, T = 1005;
  16.  
  17. int a[N], used[N], have[N];
  18. int fir[N], sec[N];
  19. vector<int> g[N], p[N], c[N], top;
  20.  
  21. void dfs(int v)
  22. {
  23.     used[v] = 1;
  24.     for (int u : g[v])
  25.         if (!used[u])
  26.             dfs(u);
  27.     top.push_back(v);
  28. }
  29.  
  30. void dfs1(int v)
  31. {
  32.     if (a[v])
  33.         return;
  34.     a[v] = 1;
  35.     int go = v;
  36.     if (v < T)
  37.         go += T;
  38.     else
  39.         go -= T;
  40.     a[go] = -1;
  41.     for (int u : g[v])
  42.         dfs1(u);
  43. }
  44.  
  45. int main()
  46. {
  47.     ios::sync_with_stdio(0); cin.tie(0);
  48.     freopen("in.txt", "r", stdin);
  49.     int n;
  50.     cin >> n;
  51.     int T = n * n;
  52.     for (int i = 0; i < n; i++)
  53.     {
  54.         int a, b, cc;
  55.         cin >> a >> b >> cc;
  56.         b--;
  57.         fir[i] = i * n + a;
  58.         sec[i] = b * i + cc;
  59.         p[i].push_back(a);
  60.         c[a].push_back(i);
  61.         p[b].push_back(cc);
  62.         c[cc].push_back(b);
  63.         g[i * n + a].push_back(T + b * n + cc);
  64.         g[T + b * n + cc].push_back(i * n + a);
  65.         have[T + i * n + a] = have[b * n + cc] = have[T + b * n + cc] = have[i * n + a] = 1;
  66.         g[b * n + cc].push_back(T + i * n + a);
  67.         g[T + i * n + a].push_back(b * n + cc);
  68.     }
  69.     for (int i = 0; i < T; i++)
  70.         for (int j = 0; j < p[i].size(); j++)
  71.             for (int k = 0; k < p[i].size(); k++)
  72.                 if (j != k)
  73.                     g[i * n + p[i][j]].push_back(T + i * n + p[i][k]);
  74.     for (int i = 0; i < T; i++)
  75.         for (int j = 0; j < c[i].size(); j++)
  76.             for (int k = 0; k < c[i].size(); k++)
  77.                 if (j != k)
  78.                     g[c[i][j] * n + i].push_back(T + c[i][k] * n + i);
  79.     for (int i = 0; i < N; i++)
  80.         if (have[i] && !used[i])
  81.             dfs(i);
  82.     for (int i = 0; i < top.size(); i++)
  83.         dfs1(top[i]);
  84.     for (int i = 0; i < n; i++)
  85.         cout << (a[fir[i]] == 2 ? "2 " : "1 ");
  86.     return 0;
  87. }
RAW Paste Data