NOI2017游戏

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 50010
  4 #define M 100010
  5 #define IL inline
  6 #define RG register 
  7 #define INF (1<<30)
  8 IL bool isitdigit(char c){    return c<=‘9‘&&c>=‘0‘;    }
  9 IL bool isitalpha(char c){    return c>=‘a‘&&c<=‘z‘;    }
 10 IL bool isitalphas(char c){    return c>=‘A‘&&c<=‘Z‘;    }
 11 IL int minify(int &a,int b){    return a<b? a:a=b;    }
 12 IL int read()
 13 {
 14     RG int s;RG char c;
 15     while(!isitdigit(c=getchar()));
 16     for(s=c-‘0‘;isitdigit(c=getchar());s=(s<<1)+(s<<3)+c-‘0‘);
 17     return s;
 18 }
 19 IL char readchar()
 20 {
 21     RG char c;
 22     while(!isitalpha(c=getchar()));
 23     return c;
 24 }
 25 IL char readchars()
 26 {
 27     RG char c;
 28     while(!isitalphas(c=getchar()));
 29     return c;
 30 }
 31 int n,m,d;
 32 int color[M],trans[N],ord[N][5],another[M][4],anothertot,uncertain[10],uncertaintot,backup[M];
 33 int head[2][M],to[10*M],next[10*M],tot;
 34 int inde,up[M],num[M];
 35 int st[M],top,belong[M],cnt,que[M],front,tail,du[M],vis[M];
 36 int opsite[M];
 37 IL void addedge(int d,int f,int t)
 38 {
 39     to[++tot]=t;
 40     next[tot]=head[d][f];
 41     head[d][f]=tot;
 42 }
 43 void tarjan(int i)
 44 {
 45     up[i]=num[i]=++inde;st[++top]=i;
 46     for(RG int j=head[0][i];j;j=next[j]) 
 47         if(!num[to[j]]) 
 48         {
 49             tarjan(to[j]);
 50             minify(up[i],up[to[j]]);
 51         }
 52         else if(!belong[to[j]])
 53             minify(up[i],num[to[j]]);
 54     if(num[i]==up[i])
 55     {
 56         cnt++;
 57         for(;st[top]!=i;--top) belong[st[top]]=cnt;
 58         belong[st[top]]=cnt;
 59         top--;
 60     }
 61 }
 62 IL bool judge()
 63 {
 64     for(RG int i=1;i<=n;++i)
 65         if(belong[i]==belong[i+n]) return 1;
 66     for(RG int i=1;i<=n+n;++i)
 67     {
 68         for(RG int j=head[0][i];j;j=next[j]) 
 69             if(belong[i]!=belong[to[j]])
 70                 addedge(1,belong[i],belong[to[j]]),du[belong[to[j]]]++;
 71     }
 72     return 0;
 73 }
 74 IL void topsort()
 75 {
 76     memset(que,0,sizeof(que));
 77     tail=0;front=1;
 78     for(RG int i=1;i<=cnt;++i) if(!du[i]) que[++tail]=i;
 79     while(front<=tail)
 80     {
 81         int i=que[front++];
 82         for(RG int j=head[1][i];j;j=next[j])
 83         {
 84             du[to[j]]--;
 85             if(!du[to[j]]) que[++tail]=to[j];
 86         }
 87     }
 88 }
 89 
 90 void dfs(int i)
 91 {
 92     vis[i]=-1;
 93     for(RG int j=head[1][i];j;j=next[j])
 94         if(!vis[to[j]])    dfs(to[j]);
 95 }
 96 
 97 
 98 void print()
 99 {
100     memset(opsite,0,sizeof(opsite));
101     for(RG int i=1;i<=n;++i) opsite[belong[i]]=belong[i+n];
102     for(RG int i=n;i<=n+n;++i) opsite[belong[i]]=belong[i-n];
103     for(RG int i=1;i<=tail;i++)
104     {
105         if(!vis[que[i]])
106         {
107             vis[que[i]]=1;
108             dfs(opsite[que[i]]);
109         }
110     }
111     for(RG int i=1;i<=n;++i)
112             printf("%c",vis[belong[i]]==1? color[i]:color[i+n]);
113 }
114 int main()
115 {
116     freopen("2sat.in","r",stdin);
117     n=read(),d=read();
118     for(int ope=1;ope<=n;++ope)
119     {
120         RG char s=readchar();
121         if(s==‘x‘) 
122         {
123             uncertain[++uncertaintot]=ope;
124             continue;
125         }
126         if(s==‘a‘)
127         {
128             ord[ope][‘B‘-‘A‘]=ope;color[ope]=‘B‘;
129             ord[ope][‘C‘-‘A‘]=ope+n;color[ope+n]=‘C‘;
130             trans[ope]=‘B‘+‘C‘-‘A‘;
131         }
132         else if(s==‘b‘)
133         {
134             ord[ope][‘A‘-‘A‘]=ope;color[ope]=‘A‘;
135             ord[ope][‘C‘-‘A‘]=ope+n;color[ope+n]=‘C‘;
136             trans[ope]=‘A‘+‘C‘-‘A‘;
137         }
138         else
139         {
140             ord[ope][‘A‘-‘A‘]=ope;color[ope]=‘A‘;
141             ord[ope][‘B‘-‘A‘]=ope+n;color[ope+n]=‘B‘;
142             trans[ope]=‘A‘+‘B‘-‘A‘;
143         }
144     }
145     m=read();
146     while(m--)
147     {
148         RG int i=read();RG char hi=readchars();RG int j=read();RG char hj=readchars();
149         if(!trans[i]&&!trans[j]) 
150         {
151             another[++anothertot][0]=i,another[anothertot][1]=hj,another[anothertot][2]=j,another[anothertot][3]=hj;
152             continue;
153         }
154         addedge(0,ord[j][hj-‘A‘],ord[i][hi-‘A‘]);
155         addedge(0,ord[i][trans[i]-hi],ord[j][trans[j]-hj]);
156     }
157     for(int i=1;i<=n;++i) backup[i]=head[0][i],backup[i+n]=head[0][i+n];
158     RG int still=tot+1;
159     for(RG int i=0;i<=(1<<uncertaintot)-1;++i)
160     {    
161         memset(head[1],0,sizeof(head[1]));
162         memset(up,0,sizeof(up));
163         memset(num,0,sizeof(num));
164         memset(st,0,sizeof(st));
165         memset(belong,0,sizeof(belong));
166         memset(du,0,sizeof(du));
167         memset(vis,0,sizeof(vis));
168         cnt=top=inde=0;
169         for(RG int j=1;j<=n;++j) head[0][j]=backup[j],head[0][j+n]=backup[j+n];
170         while(tot>=still)    to[tot]=next[tot]=0,tot--;
171         for(RG int j=0;j<uncertaintot;++j) 
172             if(i&(1<<j))
173             {
174                 ord[uncertain[j]][‘B‘-‘A‘]=uncertain[j];color[uncertain[j]]=‘B‘;
175                 ord[uncertain[j]][‘C‘-‘A‘]=uncertain[j]+n;color[uncertain[j]+n]=‘C‘;
176                 ord[uncertain[j]][‘A‘-‘A‘]=0;
177                 trans[uncertain[j]]=‘B‘+‘C‘-‘A‘;
178             }
179             else
180             {
181                 ord[uncertain[j]][‘A‘-‘A‘]=uncertain[j];color[uncertain[j]]=‘A‘;
182                 ord[uncertain[j]][‘B‘-‘A‘]=uncertain[j]+n;color[uncertain[j]+n]=‘B‘;
183                 ord[uncertain[j]][‘C‘-‘A‘]=0;
184                 trans[uncertain[j]]=‘A‘+‘B‘-‘A‘;
185             }
186         for(RG int j=1;j<=anothertot;++j) 
187             if(!ord[another[j][2]][another[j][3]-‘A‘]&&ord[another[j][0]][another[j][1]-‘A‘])
188                 addedge(0,ord[another[j][0]][trans[another[j][0]]-another[j][1]],ord[another[j][0]][another[j][1]-‘A‘]);
189             else
190             {
191                 addedge(0, ord[another[j][2]][another[j][3]-‘A‘],ord[another[j][0]][another[j][1]-‘A‘]);
192                 addedge(0,ord[another[j][0]][trans[another[j][0]]-another[j][1]],ord[another[j][2]][trans[another[j][2]]-another[j][3]]);
193             }
194         for(RG int j=1;j<=n+n;++j) if(!num[j]) tarjan(j);
195         if(judge()) continue;
196         topsort();
197         print();
198         return 0;
199     }
200     printf("-1");
201     return 0;
202 }