[NOI2017]游戏

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<vector>
  5 #define M 400010
  6 using namespace std;
  7 
  8 vector<int>S;
  9 struct point{
 10     int to,next;
 11 }e[M<<1];
 12 struct limit{
 13     int i,hi,j,hj;//i,j表示场次,hi,hj表示车型 
 14 }li[M];
 15 
 16 int n,m,num,tim,top,tot,d;
 17 int head[M],co[M],mark[M];
 18 int dfn[M],low[M],st[M];
 19 bool vis[M];
 20 bool flag=false;
 21 
 22 void add(int from,int to)
 23 {
 24     e[++num].next=head[from];
 25     e[num].to=to;
 26     head[from]=num;
 27 }
 28 
 29 void tarjan(int x)
 30 {
 31     dfn[x]=low[x]=++tim;
 32     st[++top]=x;
 33     vis[x]=true;
 34     for(int i=head[x];i;i=e[i].next)
 35     {
 36         int to=e[i].to;
 37         if(!dfn[to])
 38         {
 39             tarjan(to);
 40             low[x]=min(low[x],low[to]);
 41         }
 42         else if(vis[to]) low[x]=min(low[x],dfn[to]);
 43     }
 44     if(low[x]==dfn[x])
 45     {
 46         tot++;
 47         while(st[top+1]!=x)
 48         {
 49             co[st[top]]=tot;
 50             vis[st[top]]=false;
 51             top--;
 52         }
 53     }
 54 }
 55 
 56 void link()
 57 {
 58     for(int i=1;i<=m;i++)
 59     {
 60         if(li[i].hi==mark[li[i].i]) continue;
 61         //如果第一场比赛限制这种车的使用，就不能用了
 62         int A,AA,B,BB;
 63         //A,B当前场次能用的车1
 64         //AA,BB当前场次能用的车2 
 65         //getA
 66         if(mark[li[i].i]==1)
 67         {
 68             if(li[i].hi==2) //一辆为B车,另一辆为C车 
 69             {
 70                 A=li[i].i;
 71                 AA=A+n;
 72             }
 73             else
 74             {
 75                 A=li[i].i+n;
 76                 AA=A-n;
 77             }
 78         }
 79         else if(mark[li[i].i]==2)
 80         {
 81             if(li[i].hi==1) //一辆为A车,另一辆为C车 
 82             {
 83                 A=li[i].i;
 84                 AA=A+n;
 85             }
 86             else
 87             {
 88                 A=li[i].i+n;
 89                 AA=A-n;
 90             }
 91         }
 92         else if(mark[li[i].i]==3)
 93         {
 94             if(li[i].hi==1) //一辆为A车,另一辆为B车 
 95             {
 96                 A=li[i].i;
 97                 AA=A+n;
 98             }
 99             else
100             {
101                 A=li[i].i+n;
102                 AA=A-n;
103             }
104         }
105         //get B
106         if(mark[li[i].j]==1)
107         {
108             if(li[i].hj==2)
109             {
110                 B=li[i].j;
111                 BB=B+n;
112             }
113             else
114             {
115                 B=li[i].j+n;
116                 BB=B-n;
117             }
118         }
119         else if(mark[li[i].j]==2)
120         {
121             if(li[i].hj==1)
122             {
123                 B=li[i].j;
124                 BB=B+n;
125             }
126             else
127             {
128                 B=li[i].j+n;
129                 BB=B-n;
130             }
131         }
132         else if(mark[li[i].j]==3)
133         {
134             if(li[i].hj==1)
135             {
136                 B=li[i].j;
137                 BB=B+n;
138             }
139             else
140             {
141                 B=li[i].j+n;
142                 BB=B-n;
143             }
144         }
145         //cout<<i<<"　"<<A<<" "<<AA<<" "<<B<<" "<<BB<<endl;
146         if(li[i].hj==mark[li[i].j])//如果第二场根本不能打,那也不能打第一场 
147         {
148             add(A,AA);
149             continue;
150         }
151         else if(li[i].i==li[i].j)
152         {
153             if(li[i].hi!=li[i].hj) add(A,AA);//第一辆车不能在这场比赛中出现 
154             //否则这个条件没有意义 
155             continue;
156         }
157         add(A,B);
158         add(BB,AA);
159     }
160 }
161 
162 void clear()
163 {
164     num=0;
165     top=0;
166     tim=0;
167     tot=0;
168     memset(e,0,sizeof(e));
169     memset(co,0,sizeof(co));
170     memset(head,0,sizeof(head));
171     memset(dfn,0,sizeof(dfn));
172     memset(low,0,sizeof(low));
173     memset(st,0,sizeof(st));
174     memset(vis,0,sizeof(vis));
175 }
176 
177 void work()
178 {
179     clear();
180     link();
181     for(int i=1;i<=2*n;i++)
182         if(!dfn[i])
183             tarjan(i);
184     for(int i=1;i<=n;i++)
185         if(co[i]==co[i+n])
186             return;
187     flag=true;
188     for(int i=1;i<=n;i++)
189     {
190         if(mark[i]==1)
191         {
192             if(co[i]<co[i+n]) printf("B");
193             else printf("C");
194         }
195         else if(mark[i]==2)
196         {
197             if(co[i]<co[i+n]) printf("A"); 
198             else printf("C");
199         }
200         else
201         {
202             if(co[i]<co[i+n]) printf("A"); 
203             else printf("B");
204         }
205     }
206 }
207 
208 void dfs(int deep)
209 {
210     if(flag) return;
211     if(deep==d)
212     {
213         work();
214         return;
215     }
216     for(int i=1;i<=2;i++)
217     {
218         mark[S[deep]]=i;
219         dfs(deep+1);
220         if(flag) return;
221     }
222 }
223 
224 int get()
225 {
226     char c=getchar();
227     while(c<‘A‘||c>‘Z‘) c=getchar();
228     if(c==‘A‘) return 1;
229     else if(c==‘B‘) return 2;
230     else return 3;
231 }
232 
233 int main()
234 {
235     scanf("%d%d",&n,&d);
236     char s[M]; scanf("%s",s+1);
237     for(int i=1;i<=n;i++)
238     {
239         if(s[i]==‘x‘) S.push_back(i);
240         else mark[i]=s[i]-‘a‘+1;
241     }
242     scanf("%d",&m);
243     for(int i=1;i<=m;i++)
244     {
245         scanf("%d",&li[i].i); li[i].hi=get();
246         scanf("%d",&li[i].j); li[i].hj=get();
247     }
248     dfs(0);
249     if(!flag) printf("-1");
250     return 0;
251 }