QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#588332 | #9224. Express Eviction | Displace_ | RE | 4ms | 4828kb | C++14 | 2.2kb | 2024-09-25 09:40:09 | 2024-09-25 09:40:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
template <typename T>inline void read(T &x){
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
const int N=100000, inf=1e9;
int n, m;
char s[55][55];
int id[55][55][2], idx, S, T;
int lin[N], nxt[N], to[N], fl[N], tot=1;
inline void in(int x, int y, int z){
nxt[++tot]=lin[x]; lin[x]=tot; to[tot]=y; fl[tot]=z;
nxt[++tot]=lin[y]; lin[y]=tot; to[tot]=x; fl[tot]=0;
}
int dep[N], cur[N];
inline bool bfs(){
for(int i=1; i<=T; ++i) dep[i]=0, cur[i]=0;
dep[S]=1; cur[S]=lin[S];
queue<int> que;
que.emplace(S);
while(!que.empty()){
int x=que.front(); que.pop();
for(int i=lin[x]; i; i=nxt[i]){
int y=to[i];
if(fl[i]&&(!dep[y])){
dep[y]=dep[x]+1; cur[y]=lin[y];
if(y==T) return true;
que.emplace(y);
}
}
}
return false;
}
inline int dfs(int x, int now){
if(x==T) return now;
int ret=0;
for(int i=cur[x]; i&&ret<now; i=nxt[i]){
cur[x]=i;
int y=to[i];
if(fl[i]&&dep[y]==dep[x]+1){
int res=dfs(y, min(fl[i], now-ret));
fl[i]-=res; fl[i^1]+=res; ret+=res;
}
}
return ret;
}
int mxfl;
int main(){
// freopen("D:\\nya\\acm\\C\\test.in","r",stdin);
// freopen("D:\\nya\\acm\\C\\test.out","w",stdout);
read(n); read(m);
for(int i=1; i<=n; ++i){
scanf("%s", s[i]+1);
for(int j=1; j<=m; ++j) id[i][j][0]=++idx, id[i][j][1]=++idx;
}
S=idx+1; T=idx+2;
for(int i=1; i<=n; ++i) in(S, id[i][1][0], inf), in(id[i][m][1], T, inf);
for(int j=1; j<=m; ++j) in(id[1][j][1], T, inf), in(S, id[n][j][0], inf);
for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) in(id[i][j][0], id[i][j][1], s[i][j]=='#');
for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j){
for(int ii=1; ii<=n; ++ii) for(int jj=1; jj<=m; ++jj){
if(abs(ii-i)<=2&&abs(jj-j)<=2) in(id[i][j][1], id[ii][jj][0], inf);
}
}
while(bfs()){
int fl=dfs(S, inf);
while(fl) mxfl+=fl, fl=dfs(S, inf);
}
printf("%d\n", mxfl);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3728kb
input:
4 6 .##... .#.... ##.... ....#.
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4156kb
input:
20 30 ...########################### #..########################### ...########################### ...########################### .############################# ...########################### ...########################### #..########################### ...########################### ..#...............
output:
11
result:
ok 1 number(s): "11"
Test #3:
score: 0
Accepted
time: 4ms
memory: 4828kb
input:
35 35 ....###########...#########........ ##..#######################..#####. ....#######################..#####. ...#.....##################..#####. .##......##################.....##. .##..##..#############.....#....##. .....##..#############......##..##. ....#....#############..##..##..##. ####.....
output:
16
result:
ok 1 number(s): "16"
Test #4:
score: 0
Accepted
time: 1ms
memory: 4192kb
input:
30 20 .#..........##...... ..#......#..##...... .......#..........#. ..#......#..##...... .....#......#....... .#.........#........ ......#...#......... ..#..##..#...#...... ......#.......#..... ..#....#............ ........#..#.#...... ....##..#........... .........#.#.......# ........##.......... ...
output:
5
result:
ok 1 number(s): "5"
Test #5:
score: -100
Runtime Error
input:
50 45 ...##................##...................#.. ...#......#.#..........#.#.....####....#....# ....#.....#..............#..#..##......##..#. .....#......######........#.............#.... ......##...#...##...##.......#....#..#...##.. ...#..##.....##...###.............#..##.....# ...#......########...