QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#557132 | #2752. Neutral Ground | Tenshi | AC ✓ | 3ms | 6020kb | C++20 | 2.6kb | 2024-09-11 04:40:50 | 2024-09-11 04:40:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;
#define int ll
inline void read(int &x){
int s=0; x=1;
char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=45*45*2, M=1e5+5, INF=1e12+10;
int n, m, S, T;
int id[45][45], idx;
char g[45][45];
const int dx[]={-1, 1, 0, 0};
const int dy[]={0, 0, -1, 1};
struct Edge{
int to, c, next;
}e[M<<1];
int h[N], tot;
void add(int u, int v, int c){
e[tot].to=v, e[tot].c=c, e[tot].next=h[u], h[u]=tot++;
e[tot].to=u, e[tot].c=0, e[tot].next=h[v], h[v]=tot++;
}
int d[N], q[N], cur[N];
bool bfs(){
memset(d, -1, sizeof d);
int tt=-1, hh=0;
q[++tt]=S, d[S]=0, cur[S]=h[S];
while(tt>=hh){
int hd=q[hh++];
for(int i=h[hd]; ~i; i=e[i].next){
int go=e[i].to;
if(d[go]==-1 && e[i].c){
d[go]=d[hd]+1;
cur[go]=h[go];
if(go==T) return true;
q[++tt]=go;
}
}
}
return false;
}
int find(int u, int limit){
if(u==T) return limit;
int flow=0;
for(int i=cur[u]; ~i && flow<limit; i=e[i].next){
cur[u]=i;
int go=e[i].to;
if(d[go]==d[u]+1 && e[i].c){
int t=find(go, min(e[i].c, limit-flow));
if(!t) d[go]=-1;
e[i].c-=t, e[i^1].c+=t, flow+=t;
}
}
return flow;
}
int dinic(){
int res=0, flow;
while(bfs()) while(flow=find(S, INF)) res+=flow;
return res;
}
int val(char c){
if(isdigit(c)) return c-'0';
return INF;
}
signed main(){
memset(h, -1, sizeof h);
cin>>n>>m;
swap(n, m);
S=0, T=2*n*m+1;
rep(i, 1, n) rep(j, 1, m){
cin>>g[i][j];
id[i][j]=++idx;
}
rep(i, 1, n) rep(j, 1, m){
add(id[i][j], id[i][j]+idx, val(g[i][j]));
// add(id[i][j], id[i][j]+idx, INF, 0);
if(g[i][j]=='A') add(S, id[i][j], INF);
if(g[i][j]=='B') add(id[i][j]+idx, T, INF);
rep(k, 0, 3){
int ii=i+dx[k], jj=j+dy[k];
if(!id[ii][jj]) continue;
int u=id[i][j], v=id[ii][jj];
if(g[i][j]=='A'){
add(u+idx, v, INF);
}
else if(g[i][j]!='B'){
if(g[ii][jj]!='A'){
add(u+idx, v, INF);
}
}
}
}
cout<<dinic()<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3668kb
input:
8 5 A11111AA AA7B111A 111BB111 11BBB111 11BBB11B
output:
13
result:
ok single line: '13'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
25 6 A211111321231111111111111 2A2111110001111111BB11111 AA211111000111111BBBB1111 A2111114111411111BBBB1111 AA2111110001111111BB11111 AA21111110111111111111111
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
10 10 9999999999 9999999999 9999999999 11B0999999 1000999999 1999999999 1999990999 199990A099 1999991999 1111111999
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 2ms
memory: 4096kb
input:
40 40 A111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 111111111111111111111111111111111111111A 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111...
output:
25
result:
ok single line: '25'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5904kb
input:
40 40 A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9 9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9 9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9 9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9 9B9A9B9...
output:
7200
result:
ok single line: '7200'
Test #6:
score: 0
Accepted
time: 0ms
memory: 6020kb
input:
40 40 A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0 0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0 0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0 0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0 0B0A0B0...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
40 40 A111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 111111111111111111111111111111111111111A 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1111111...
output:
27
result:
ok single line: '27'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
8 6 99999999 11B89999 19990009 19990A09 19999199 11111199
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
10 20 7436199416 0740828365 3BB97AAA56 BB1050A576 BB09AAAA59 9436A7A594 870752A305 17311AAA18 300778AA80 694AAAA920 829AA67466 9AAA816697 AAAA5BBB89 AAAA5BBB94 7AA6BBBB47 AAA5B0BBB0 2A0BB1BB05 372BB91B62 3595BBBBBB 357BBBBBB9
output:
56
result:
ok single line: '56'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
20 10 13BBBBB8683006374919 4BB2B237281364446735 BBB97700668962755468 B4428083260BB2086623 2AAAA777BBBBBBB49548 8AAAA9A5BBBBBBBBB202 AAAAAAA2BBBBBBBBB402 8AAAAAA69BBB3BB28218 AAAAAAA83BB38BBB3359 AAAAAAA7999455827606
output:
49
result:
ok single line: '49'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
20 20 25856295408107772399 35893013789856837104 39164180311582356777 42396356552896556340 87301639504573750650 36149965146808550936 46668126767624245842 81785A87739588198960 58978AAAA55552271341 449902AA133983981669 09702AAA415039084066 56057AAAA04537698341 10580AAAA7054BB87604 85998AAAA3815BBBB178 ...
output:
47
result:
ok single line: '47'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
30 20 83272382997532854470AAA2081085 55418167116020216737AAAA836122 08615309275630600141AAA3750137 10412727935316509926AAA8213842 946090169942907317670292352638 473669321729065940959047626928 966175998987030436453643678467 959428364139218626723848883353 360180877508819524157455721160 8B2465420154488...
output:
26
result:
ok single line: '26'
Test #13:
score: 0
Accepted
time: 2ms
memory: 4020kb
input:
35 35 71439710038840545765840866706615187 87011124136864908978528863143370418 72463503519784A64766554520801522357 67336355780600AA4A17316394465519317 40340535175910AAAAA4920444132787303 3887020407108748A6A8174316547499885 155219950383942AA5A1534978388940968 0348016997AA424AAA05188851894551568 861497...
output:
41
result:
ok single line: '41'
Test #14:
score: 0
Accepted
time: 3ms
memory: 4144kb
input:
40 40 0679221947731249959969433845432750656124 4379325056263218235062679461823907756941 8621910410306401844044524168766281673138 3112229466003110829374745773576090285698 0628020663404653026560929857657748975624 7663359924019535309405104891364250469737 0AA6694896753027751014062836968001610487 2396239...
output:
55
result:
ok single line: '55'