QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#129892 | #5250. Combination Locks | TadijaSebez | WA | 1ms | 3748kb | C++14 | 2.4kb | 2023-07-23 03:59:23 | 2023-07-23 03:59:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
char a[15],b[15],s[15];
const int N=1050;
const int inf=1e9+7;
bool ban[N],was[N];
int totalA,totalB;
int src,dest;
struct Edge{
int u,v,c,f;
};
vector<Edge> edges;
vector<int> E[N];
void AddEdge(int u,int v,int c){
E[u].pb(edges.size());
edges.pb(Edge{u,v,c,0});
edges.pb(Edge{v,u,0,0});
}
int dist[N],ptr[N];
int DFS(int u,int flow){
if(u==dest)return flow;
if(dist[u]>=dist[dest])return 0;
int ans=0;
for(;ptr[u]<E[u].size();ptr[u]++){
int e=E[u][ptr[u]];
int cap=edges[e].c-edges[e].f;
int v=edges[e].v;
if(cap==0 || dist[v]!=dist[u]+1)continue;
int cut=DFS(v,min(flow,cap));
flow-=cut;
ans+=cut;
edges[e].f+=cut;
edges[e^1].f-=cut;
if(flow==0){
return ans;
}
}
return ans;
}
bool BFS(){
for(int i=0;i<=dest;i++){
dist[i]=-1;
ptr[i]=0;
}
queue<int> q;
q.push(src);
dist[src]=0;
while(q.size()){
int u=q.front();
q.pop();
for(auto e:E[u]){
int v=edges[e].v;
int cap=edges[e].c-edges[e].f;
if(cap!=0 && dist[v]==-1){
dist[v]=dist[u]+1;
q.push(v);
}
}
}
return dist[dest]!=-1;
}
int MaxFlow(){
int ans=0;
while(BFS()){
ans+=DFS(src,inf);
}
return ans;
}
void Build(int u,int n,int parity){
if(was[u])return;
int p=__builtin_popcount(u)&1;
if(p==parity){
totalA++;
AddEdge(src,u,1);
}else{
totalB++;
AddEdge(u,dest,1);
}
was[u]=true;
for(int i=0;i<n;i++){
int v=u^(1<<i);
if(ban[v])continue;
if(p==parity){
AddEdge(u,v,inf);
}
Build(v,n,parity);
}
}
int main(){
int t;
scanf("%i",&t);
while(t--){
int n,c;
scanf("%i %i",&n,&c);
scanf("%s",a);
scanf("%s",b);
int mask=0;
for(int i=0;i<n;i++){
if(a[i]==b[i]){
mask|=1<<i;
}
}
for(int j=0;j<c;j++){
scanf("%s",s);
int m=0;
for(int i=0;i<n;i++){
if(s[i]=='='){
m|=1<<i;
}
}
ban[m]=true;
}
src=(1<<n);
dest=(1<<n)+1;
totalA=0;
totalB=0;
Build(mask,n,__builtin_popcount(mask)&1);
int flow=MaxFlow();
if(flow==totalA || (flow==totalA-1 && totalB>=totalA)){
printf("Alice\n");
}else{
printf("Bob\n");
}
for(int i=0;i<(1<<n);i++){
ban[i]=false;
was[i]=false;
}
for(int i=0;i<=dest;i++){
E[i].clear();
}
edges.clear();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3664kb
input:
2 1 0 0 0 1 1 0 0 .
output:
Alice Bob
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
8 2 0 00 00 2 1 00 00 .. 2 1 00 00 =. 2 2 00 00 .. =. 2 1 00 00 .= 2 2 00 00 .. .= 2 2 00 00 =. .= 2 3 00 00 .. =. .=
output:
Alice Alice Bob Alice Bob Alice Bob Bob
result:
ok 8 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
20 4 4 4714 5245 ..=. ..== .==. ==.. 4 1 2697 1438 .=.. 4 5 9255 0677 ...= ..== =..= ==.= ==== 4 12 3292 7326 ...= ..=. ..== .=.. .=.= .==. =... =..= =.== ==.. ==.= ==== 4 9 8455 2536 ...= ..== .=.. .=.= .==. .=== =... ==.. ===. 4 12 5755 1517 ...= ..=. ..== .=.. .=.= .=== =..= =.=. =.== ==.. ==.= =...
output:
Alice Bob Alice Bob Bob Alice Bob Bob Alice Alice Bob Alice Alice Bob Bob Bob Bob Bob Bob Bob
result:
ok 20 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
20 5 30 99942 90170 ..... ....= ...== ..=.. ..=.= ..==. ..=== .=... .=..= .=.=. .=.== .==.. .==.= .===. .==== =...= =..=. =..== =.=.. =.=.= =.==. =.=== ==... ==..= ==.=. ==.== ===.. ===.= ====. ===== 5 14 11760 95480 ...=. ...== ..=.. ..=.= .=... .=..= .==== =.... =...= =.=.. =.==. ==... ==.== =====...
output:
Bob Alice Alice Alice Alice Bob Bob Bob Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Bob
result:
ok 20 lines
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3748kb
input:
20 6 62 188256 588825 ...... .....= ....=. ....== ...=.. ...=.= ...==. ...=== ..=... ..=..= ..=.=. ..=.== ..==.. ..==.= ..===. ..==== .=.... .=...= .=..=. .=..== .=.=.. .=.=.= .=.==. .=.=== .==..= .==.=. .==.== .===.. .===.= .===== =..... =....= =...=. =...== =..=.. =..=.= =..==. =..=== =.=... =.=.....
output:
Bob Bob Alice Bob Alice Bob Bob Bob Bob Alice Bob Bob Alice Alice Bob Bob Alice Alice Bob Bob
result:
wrong answer 4th lines differ - expected: 'Alice', found: 'Bob'