Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define P(x,y) make_pair(x,y)
- using namespace std;
- class TwoSAT{
- public :
- int n , timer , cnt;
- vector < vector < int > > v ;
- vector < set < int > > adj;
- vector < int > low , vi , comp , depth ;
- stack < int > S;
- void Fix(vector < int > &vec , int V){
- vec.resize(n*2);
- fill(vec.begin() , vec.end() , V);
- }
- void init(int N){
- n = N; timer=0; cnt=-1;
- v.clear(); v.resize(n*2); for(int j=0;j<n*2;j++) v[j].clear();
- adj.clear(); adj.resize(n*2); for(int j=0;j<n*2;j++) adj[j].clear();
- Fix(depth , -1);
- Fix(comp , 0);
- Fix(low , 0);
- Fix(vi , 0);
- }
- void addedge(int a , int b){
- v[a^1].push_back(b);
- v[b^1].push_back(a);
- }
- void add(int a , int na , int b , int nb){
- a--; b--;
- a*=2; b*=2;
- a+=na; b+=nb;
- addedge(a , b);
- }
- void addxor(int a , int na , int b , int nb){
- compadd(a , na , b , nb^1 , a , na^1 , b , nb);
- }
- void addimp(int a , int na , int b , int nb){
- a--; b--;
- a*=2; b*=2;
- a+=na; b+=nb;
- v[a].push_back(b);
- }
- void compadd(int a , int na , int b , int nb , int c , int nc , int d , int nd){
- add(a , na , c , nc);
- add(a , na , d , nd);
- add(b , nb , c , nc);
- add(b , nb , d , nd);
- }
- void dfs(int x){
- depth[x] = low[x] = ++timer; vi[x] = 1; S.push(x);
- for(auto nxt : v[x]){
- if(depth[nxt] == -1){
- dfs(nxt);
- low[x] = min(low[x] , low[nxt]);
- }
- else if(vi[nxt]) low[x] = min(low[x] , depth[nxt]);
- }
- if(depth[x] != low[x]) return;
- ++cnt;
- while(1){
- int node = S.top(); S.pop();
- comp[node] = cnt; vi[node] = 0;
- if(node == x) break;
- }
- }
- bool Satisfable(){
- for(int j=0;j<n*2;j++)
- if(depth[j] == -1)
- dfs(j);
- for(int j=0;j<n;j++)
- if(comp[j] == comp[j^1])
- return false;
- return true;
- }
- void build_graph(){
- fill(vi.begin() , vi.end() , 0);
- for(int x=0;x<n*2;x++)
- for(auto nxt : v[x])
- if(comp[x] != comp[nxt])
- adj[comp[x]].insert(comp[nxt]);
- for(int x=0;x<=cnt;x++)
- for(auto nxt : adj[x])
- vi[nxt]++;
- }
- void Topo(){
- queue < int > Q;
- for(int j=0;j<=cnt;j++)
- if(vi[j] == 0)
- Q.push(j);
- fill(depth.begin() , depth.end() , 0);
- timer=0;
- while(!Q.empty()){
- int x = Q.front(); Q.pop();
- depth[x] = ++timer;
- for(auto nxt : adj[x]){
- vi[nxt] -- ;
- if(vi[nxt] == 0) Q.push(nxt);
- }
- }
- }
- void solution(vector < int > &sol){
- build_graph();
- Topo();
- sol.resize(n);
- for(int j=0;j<n*2;j+=2){
- if(depth[comp[j]] < depth[comp[j^1]])
- sol[j/2] = 0;
- else sol[j/2] =1;
- }
- }
- };
- #define mx 200001
- int col[mx];
- int ar[2*mx];
- vector<int> A[mx];
- bool T[mx];
- TwoSAT sol;
- void add(int x, int y){
- if(col[ar[x]]!= col[ar[y]] || ar[x]==ar[y]) return ;
- sol.addxor(ar[x],!T[x],ar[y],!T[y]);
- // printf("%d %d %d %d\n",ar[x], int(!T[x]),ar[y], int(!T[y]) );
- }
- int main(){
- freopen("chip.in","r",stdin); freopen("chip.out","w",stdout);
- int n;
- scanf("%d", &n);
- sol.init(n);
- for(int i=1;i<=n;++i){
- scanf("%d", &col[i]);
- }
- for(int i=1;i<=2*n;++i){
- scanf("%d", &ar[i]);
- T[i]= (A[ar[i]].size()>0);
- A[ar[i]].push_back(i);
- if(i>1) add(i,i-1);
- }
- add(2*n,1);
- vector<int> S;
- if(sol.Satisfable()){
- sol.solution(S);
- printf("YES\n");
- for(int i=1;i<=n;++i)
- printf("%d ", A[i][S[i-1]]);
- }
- else printf("NO\n");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement