Advertisement
Guest User

Untitled

a guest
May 3rd, 2016
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.04 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define P(x,y) make_pair(x,y)
  3. using namespace std;
  4. class TwoSAT{
  5. public :
  6. int n , timer , cnt;
  7. vector < vector < int > > v ;
  8. vector < set < int > > adj;
  9. vector < int > low , vi , comp , depth ;
  10. stack < int > S;
  11. void Fix(vector < int > &vec , int V){
  12. vec.resize(n*2);
  13. fill(vec.begin() , vec.end() , V);
  14. }
  15. void init(int N){
  16. n = N; timer=0; cnt=-1;
  17. v.clear(); v.resize(n*2); for(int j=0;j<n*2;j++) v[j].clear();
  18. adj.clear(); adj.resize(n*2); for(int j=0;j<n*2;j++) adj[j].clear();
  19. Fix(depth , -1);
  20. Fix(comp , 0);
  21. Fix(low , 0);
  22. Fix(vi , 0);
  23. }
  24. void addedge(int a , int b){
  25. v[a^1].push_back(b);
  26. v[b^1].push_back(a);
  27. }
  28. void add(int a , int na , int b , int nb){
  29. a--; b--;
  30. a*=2; b*=2;
  31. a+=na; b+=nb;
  32. addedge(a , b);
  33. }
  34. void addxor(int a , int na , int b , int nb){
  35. compadd(a , na , b , nb^1 , a , na^1 , b , nb);
  36. }
  37. void addimp(int a , int na , int b , int nb){
  38. a--; b--;
  39. a*=2; b*=2;
  40. a+=na; b+=nb;
  41. v[a].push_back(b);
  42. }
  43. void compadd(int a , int na , int b , int nb , int c , int nc , int d , int nd){
  44. add(a , na , c , nc);
  45. add(a , na , d , nd);
  46. add(b , nb , c , nc);
  47. add(b , nb , d , nd);
  48. }
  49. void dfs(int x){
  50. depth[x] = low[x] = ++timer; vi[x] = 1; S.push(x);
  51. for(auto nxt : v[x]){
  52. if(depth[nxt] == -1){
  53. dfs(nxt);
  54. low[x] = min(low[x] , low[nxt]);
  55. }
  56. else if(vi[nxt]) low[x] = min(low[x] , depth[nxt]);
  57. }
  58. if(depth[x] != low[x]) return;
  59. ++cnt;
  60. while(1){
  61. int node = S.top(); S.pop();
  62. comp[node] = cnt; vi[node] = 0;
  63. if(node == x) break;
  64. }
  65. }
  66. bool Satisfable(){
  67. for(int j=0;j<n*2;j++)
  68. if(depth[j] == -1)
  69. dfs(j);
  70. for(int j=0;j<n;j++)
  71. if(comp[j] == comp[j^1])
  72. return false;
  73. return true;
  74. }
  75. void build_graph(){
  76. fill(vi.begin() , vi.end() , 0);
  77. for(int x=0;x<n*2;x++)
  78. for(auto nxt : v[x])
  79. if(comp[x] != comp[nxt])
  80. adj[comp[x]].insert(comp[nxt]);
  81. for(int x=0;x<=cnt;x++)
  82. for(auto nxt : adj[x])
  83. vi[nxt]++;
  84. }
  85. void Topo(){
  86. queue < int > Q;
  87. for(int j=0;j<=cnt;j++)
  88. if(vi[j] == 0)
  89. Q.push(j);
  90. fill(depth.begin() , depth.end() , 0);
  91. timer=0;
  92. while(!Q.empty()){
  93. int x = Q.front(); Q.pop();
  94. depth[x] = ++timer;
  95. for(auto nxt : adj[x]){
  96. vi[nxt] -- ;
  97. if(vi[nxt] == 0) Q.push(nxt);
  98. }
  99. }
  100. }
  101. void solution(vector < int > &sol){
  102. build_graph();
  103. Topo();
  104. sol.resize(n);
  105. for(int j=0;j<n*2;j+=2){
  106. if(depth[comp[j]] < depth[comp[j^1]])
  107. sol[j/2] = 0;
  108. else sol[j/2] =1;
  109. }
  110. }
  111. };
  112.  
  113. #define mx 200001
  114. int col[mx];
  115. int ar[2*mx];
  116. vector<int> A[mx];
  117. bool T[mx];
  118. TwoSAT sol;
  119. void add(int x, int y){
  120. if(col[ar[x]]!= col[ar[y]] || ar[x]==ar[y]) return ;
  121. sol.addxor(ar[x],!T[x],ar[y],!T[y]);
  122. // printf("%d %d %d %d\n",ar[x], int(!T[x]),ar[y], int(!T[y]) );
  123. }
  124.  
  125. int main(){
  126.  
  127. freopen("chip.in","r",stdin); freopen("chip.out","w",stdout);
  128. int n;
  129. scanf("%d", &n);
  130. sol.init(n);
  131. for(int i=1;i<=n;++i){
  132. scanf("%d", &col[i]);
  133. }
  134. for(int i=1;i<=2*n;++i){
  135. scanf("%d", &ar[i]);
  136. T[i]= (A[ar[i]].size()>0);
  137. A[ar[i]].push_back(i);
  138. if(i>1) add(i,i-1);
  139. }
  140. add(2*n,1);
  141. vector<int> S;
  142.  
  143. if(sol.Satisfable()){
  144. sol.solution(S);
  145. printf("YES\n");
  146. for(int i=1;i<=n;++i)
  147. printf("%d ", A[i][S[i-1]]);
  148. }
  149. else printf("NO\n");
  150. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement