QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#789142 | #9665. Black-White Cubic Lattice | rotcar07 | AC ✓ | 97ms | 4668kb | C++23 | 1.6kb | 2024-11-27 19:24:17 | 2024-11-27 19:24:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int N=5005;
int n,m,l;
typedef long long ll;
constexpr ll inf=1e9,Inf=1e13;
constexpr int maxn=5005,maxm=1e5+5;
int s,t,tot=1,fir[maxn],to[maxm],nxt[maxm];ll val[maxm];
inline void addedge(int u,int v,ll w){++tot,nxt[tot]=fir[u],fir[u]=tot,to[tot]=v,val[tot]=w;}
inline void add(int u,int v,ll w){addedge(u,v,w),addedge(v,u,0);}
int dep[maxn],firr[maxn];
inline bool bfs(){
memcpy(firr,fir,sizeof fir);
memset(dep,0,sizeof dep);dep[s]=1;
queue<int> q;q.push(s);
while(!q.empty()){
int p=q.front();q.pop();
if(p==t) return 1;
for(int i=fir[p];i;i=nxt[i])if(!dep[to[i]]&&val[i]) dep[to[i]]=dep[p]+1,q.push(to[i]);
}
return 0;
}
ll dfs(int p,ll res){
if(p==t) return res;
ll fl=0;
for(int &i=firr[p];i;i=nxt[i])if(dep[to[i]]==dep[p]+1&&val[i]){
ll z=dfs(to[i],min(res,val[i]));
res-=z,fl+=z,val[i]-=z,val[i^1]+=z;
}
if(!fl) dep[p]=0;
return fl;
}
int main(){
cin>>n>>m>>l;
vector<int> v;v.push_back(0);
for(int i=1;i<=l*n;i++){
string s;cin>>s;
for(char c:s) v.emplace_back(c=='W');
}
s=0,t=n*m*l+1;
ll ans=-inf*n*m*l;
for(int i=0;i<l*n;i++){
for(int j=1;j<=m;j++){
int x=i*m+j,y;cin>>y;
add(s,x,x==n*m*l?Inf:inf+(v[x]?y:0));
add(x,t,x==1?Inf:inf+(v[x]?0:y));
if(j<m) add(x,x+1,Inf);
if(i%n!=n-1) add(x,x+m,Inf);
if(i/n!=l-1) add(x,x+n*m,Inf);
}
}
while(bfs()) ans+=dfs(s,1e18);
cout<<ans<<'\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
input:
2 2 2 WW WW BB BB 1 1 1 1 2 2 2 2
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3520kb
input:
2 1 1 W B 0 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 19ms
memory: 4548kb
input:
1 1 5000 B W W W W W W W W B B B W B W B W B W W B W W B B W B B B B W W W W W W W B B B B B B B B B W B B W B B B W W B B W W W W W W W B B B B W B B W B W W W W W B B W B B W W B W B B B B W W W B B W B W W W W W B W B B B W W B W B B W B W B B B B B W B B W W W W B W B W B W B W B B W B B B W W W...
output:
1218
result:
ok single line: '1218'
Test #4:
score: 0
Accepted
time: 17ms
memory: 4192kb
input:
5000 1 1 B W B W B B B B W W W W B W W W W W W W B B B B B B W W W B B B B B B B W B W B W B B W B B W B B B W B W B B B B W B W W B W B W B W W W W B B W W W B W W W W B W B W B W W W W B B W B W B W B B W W W B B B B W W W B W B W B B B W B W B W B B B W B W B B B W B B B B W W B W B W W W W W B W...
output:
242900000
result:
ok single line: '242900000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 4340kb
input:
1 5000 1 WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...
output:
100000
result:
ok single line: '100000'
Test #6:
score: 0
Accepted
time: 89ms
memory: 4388kb
input:
2 2500 1 BWBBWWWBBBWBWBBBBBBBWBBBBBWWWWBBWBWWBBBBBBBBBWBWBWBBWWBBWWWBBWWWBBWWWWBWBBBWWBWBWBWWBBBWBWWWWWWWWWBBBBWWWBBBBWWBWBWBWBWBWWBWBBBBBBWBBWWWBWWBWWBWWBWWWBWWWBBBBBBBWBBWWBWWWWWWWBBBBWWBBBBBWWWBBBBBBWBWWWBWWWWBBBBWWWWWBWWBBBBWWWBWWBBWBWBBWWWBBBWWBBWBBWWBWWBBWBWBBWBWWWBWWWWWBBWWWBWWWWWWBWWWBBBWWBW...
output:
12335546
result:
ok single line: '12335546'
Test #7:
score: 0
Accepted
time: 97ms
memory: 4288kb
input:
1666 3 1 WBB WWB BWB BWW WWB WWB BBB BBB BBW WBB BBB BBW BWW WWB BBB BBW WWW BBW WWW BWW BWB WWB BWB WWW BWB BWW WWB BWW BWB BBB BBW BBB BWB WWB WBW WWB BWB BWW BWB WWW BBW BBW BBW BWW BWB BBB WWB BBB BBB WBB BBW BBB BBW BBB BBB WBW BBW WBW BBB BWB WBW BBW WWW WWW WWW BWB WWB BBW WBB WWB BWW BBW WBW...
output:
11971988
result:
ok single line: '11971988'
Test #8:
score: 0
Accepted
time: 91ms
memory: 4292kb
input:
4 1 1250 W B W B B W B B B W B B W W W W B B B B W B B B B W W B W W B W W B W W B B W B B W B B W B W W B W W B W B W B W W W B B B W W B B W B B B W B B W W W B B W B W B B B W B B W B W B B B B B W W W B W B W W W W B W B W B B B W W B W W W W W B B B B B W W W W B B W W W W W B B B B B B W W W B...
output:
12131611
result:
ok single line: '12131611'
Test #9:
score: 0
Accepted
time: 26ms
memory: 4340kb
input:
70 71 1 WBBWBBBWWBBBWWWBBBWWBWWWBWBBBWBWWWWWBWWBBWBWWWBWBWWBBWWBBWWBBBWBWWWWWWB WWBBBWWBWWBWBBWBBWWWWBBBWWWBBWWBBWWWWWBWWWBWWBWWBWBWWBBWWBBWBWWBWBWBBWW BWWWBWBBBBWWWWWWBWWBBWWBWWWWWBWWWWBBWBBWBWBWWBWWBBBBWBBBBWBBWWWWBBBBWWB BWBWBWBBWWWBBWWBBWWBWWBBWWBWBBWBWBBWBWWBWWBBBWBWWWBBWBBBWWWBBWBBBWWWBBW WWWW...
output:
11904642
result:
ok single line: '11904642'
Test #10:
score: 0
Accepted
time: 55ms
memory: 4248kb
input:
12 4 95 BBWW WBWW BWBW WWBW BWBB BWBW WBWW BWWB WWBW BWBW WWWB BWBW WWWB WBWB BWBB BBBW WBBB BWWW BWWW BBWW WWBW WBWB WWBB WWWW WBWW BBBW WBBB WWWW WBBW BBBB WWBB WBWW WWWW BBWW WBBW WWBW WWWB WWWB BWWW BWWW BWWB BWBW BBBB WWWB WBBB WWWB WWWW WBWB WWWB BBBB WWBB WBBW BBWB BBWB WWWW WWBW WBWW WBWW WW...
output:
10402
result:
ok single line: '10402'
Test #11:
score: 0
Accepted
time: 17ms
memory: 4640kb
input:
25 10 20 BBWBWBWBBW BBBWBBWBWW WBWBWBWWWB WBWBBWBWBW WWWWWWWBWB BBWBWBWWBB BBBBBWBWWB BWWWWBWWBW BWBBBBWWWW WWBBWBWBWW WWBWWWBBWW BWBWWBBWBB BBWBBWBWWB WBBBBBWWWW BBWWBBBWWB WWWWBWWWWB WBBBWWBWBW WBBWBWWBBB BBWBWWBBWW WWBWBWBWWB BBBBWWBWBB WWWWWWBBWB WWWBWWBBBW WBBWWWWBWW BBBWWWBWWB BWWWBWBBBB BBBWW...
output:
11106
result:
ok single line: '11106'
Test #12:
score: 0
Accepted
time: 33ms
memory: 4236kb
input:
50 2 50 BB WB BB BB BB BW BW WW BB WB WW BW WB BB BW WW BW BW BB WB WB BW WB WB WW WW WB BB WW BW WB BW WW BB BW BB BW BB WB WW WW WW BB WW BW BB BB BB BB WB BW WW WB BW BW BW WW WB BB WW WW BB WW BB WB BB BW BB BB WB WW BB WW WB WB WW WW BB BW WB WB WW WB WB WB WB BB WB WW BW WW BB WB BW BW WB WB W...
output:
11686
result:
ok single line: '11686'
Test #13:
score: 0
Accepted
time: 68ms
memory: 4308kb
input:
4 5 210 BWBWW BBBWW WBWWW WBWWW WBWBB BWBWW BBBWB WBBWB BWWWB BWBBB BWBBB WBBBB BBBBB WWBWB WBBBW WBWWB WBBBB BBWBB BWWBB WBBWW WWWBW WBBBW WWBBB WWBBB WWBWB BWBWW BWBBB BWWBB BBWBB BWWWB WWBBW WBBBB WBWBW BBWBW WBBBB BWBWW BBBWW BBWWW WWBBB WWWWB WWWBB BBBWB WWBWB BBWBW BBBBB BBBBB WWWWW BBWBB WWBW...
output:
9895
result:
ok single line: '9895'
Test #14:
score: 0
Accepted
time: 18ms
memory: 4364kb
input:
15 43 7 BWWWWBWBWBBBWWWWWBWBWBBBBBWWBBBBWWBWBWWBWBW BBWBWBWBBBWBBWWWWBWWWWWWBBBBBWWBWBWWWBBBWWB BWBBWBBBBBWBBWBBBWBBBBBBBWBBBBBWWWWBBBBBBBW BWBWWBBWBWBBBBWBBWBWWWWWWWBBWBWWBWBBWBBWBBB BBWWWBWWWBWWBWWBBWWWWWWWWBBWWWWWWBWBBBWWWBB WBWWBWBWBWWBWWWWWWWWBWWWBWWWWWBWWBBWBBBBWBW BBBBWWWBBWBBBBBBWWWBWBWWBBWW...
output:
10218
result:
ok single line: '10218'
Test #15:
score: 0
Accepted
time: 54ms
memory: 4444kb
input:
10 10 50 BBBBWWBBWW BWBBWBWWBB WWBBWWWWBB WBWWBBWWBW WBWBWBWBWW BBWBWWBWBB BWBWBBWBBB WWWBWBBBBW WBWWBBWWBW BWWWWBBWBB WWWWBWWWBW BBWBWWWBWB WWWWWWWBBB WBBBWWWWBB WWWBWBBBBW BWWWBWWWBB WWBBBBBBWB BWBBWBWWWB BBWWWWWWWB WWBWWBBWWW BWWWBWWBBB WWBBWWWBBB WWWBWWBWWW BWBWWBBWBW BBBBBWBWBW WBWWWWWBBB BBBBB...
output:
113532736
result:
ok single line: '113532736'
Test #16:
score: 0
Accepted
time: 19ms
memory: 4668kb
input:
16 17 18 WBWBWBWBWWWWBBWBB BBWBBWWWWBWBWBBBW BBWBWBBBBBWBWWBWB WBBBBBWWBBBBBWWBB WBBWWWWBWBWBWWWBW WBBWWWWWWBWWBWWBW WWBBBBBBBWWBBWBWB WWBWBWWWBWWWWBWBW BBBBBBBBBBWWWBBBW WWBBWBWBBWBBWBWWW WBBWBBBBBBWWWWWBW BBBBWWBBWBBBBBBBB WBWWBWWWBBWWWBWBW WBBWBBBBWBWBWBBWB WBBBWBWBWBBBWWWWB WWBWBWWWWBWWBWBWB WWB...
output:
109472675
result:
ok single line: '109472675'
Test #17:
score: 0
Accepted
time: 3ms
memory: 4660kb
input:
17 17 17 BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBB...
output:
100000
result:
ok single line: '100000'
Test #18:
score: 0
Accepted
time: 7ms
memory: 4444kb
input:
17 17 17 WWWBBBBWWBBBWWBWW WWWWBBBBBWBBBBBWW BWWWBBWWBWBWBWWWW WBBBBWBWWBWBWWWWB BWWBWWWWWBWBBBBWW WBBBWWBBBBWBBBWWB BWWWBBBBWWBWBWBWW WWBWBWBBBBWBWBBBW WWBWWWBWBBWBWWWBW BWWBBWWBBBWBWBWWB BBBWBBBWWBWBWBWWB WWWBWWWBBWBBWWWBB WBBBWBWBBBWWWBBBW WBWBWBBBWBWBBWWWW BBBWWBWWBWWBWBBBB WBBBWBBWBBWBBBWBB WWW...
output:
1128
result:
ok single line: '1128'
Test #19:
score: 0
Accepted
time: 13ms
memory: 4464kb
input:
17 17 17 WWWBBWWBBWBWWBWWB BWWBBBWWWWWWWBWBB WWWBWBBBBBWWWWWBB WWWWWWBWBBBBWWWBW WBWWBBWWWBBWBWWWB BWBBWWWBBWWWBBBBW WBBBBWBWWWBWWWBBB WWWWWWWWBBWWWWWBW WWWWBBWBWWWWWBWWB BBBBBBWWBBBWBBBWW BBBBBBBBBWWWWWWWB BBWWWWBBWWBBWWBBB WBWBBBBWWBWBBWWBB BBBBWBWWWBBBBBBWB BWBWWWBBWWBBWBWBB BBWWWBWWBWBWWBWBB WBB...
output:
5346
result:
ok single line: '5346'
Test #20:
score: 0
Accepted
time: 25ms
memory: 4448kb
input:
17 17 17 WWBBWWWWWBWWWBBBW BWWWWWWBWBWWBBWWW WWWWWBWBWBWWWWWBW WWWWBWBBBBWBWWWWW BBBBWBBWWWWWBWWWW WBWWBWWWBBBBBWBBW BBWWWWWBWBBBBWBBW BWWBBBWBWWWBBWWBW WWBBWWWBBWWBBWBWB WBBBWBWBBBBBBBBWW BWWBWBBWBWWBWBBBB WWWBWWWWWBWBBWWWW BBBBBBWBWWWBWBBBB WWWWWBBBBBBWWWWWB BWBBWWWBWBBWWBBWB WBWBBBBBWBWBWWBBB WWW...
output:
113499454
result:
ok single line: '113499454'
Extra Test:
score: 0
Extra Test Passed