QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#545018 | #9224. Express Eviction | Ashbourne | WA | 2ms | 4340kb | C++14 | 2.3kb | 2024-09-02 21:50:04 | 2024-09-02 21:50:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e8;
class Dinic{
private:
struct Edge{
int to, rev, cap;
};
vector<vector<Edge>> graph;
vector<vector<Edge>::iterator> cur;
vector<int> dist;
queue<int> que;
int n, S, T;
bool bfs(void){
for(int i = 1; i <= n; ++ i) cur[i] = graph[i].begin(), dist[i] = INT_MAX;
dist[S] = 0; que.push(S);
while(!que.empty()){
int p = que.front();
que.pop();
for(auto i : graph[p])
if(i.cap && dist[i.to] > dist[p] + 1)
dist[i.to] = dist[p] + 1, que.push(i.to);
}
return dist[T] != INT_MAX;
}
int dfs(int p, int rest){
if(p == T || !rest) return rest;
int c, used = 0;
for(auto i = cur[p]; i != graph[p].end() && rest; ++ i){
cur[p] = i;
if(!i->cap || dist[i->to] != dist[p] + 1) continue;
if(!(c = dfs(i->to, min(rest, i->cap)))) dist[i->to] = -1;
i->cap -=c; graph[i->to][i->rev].cap += c, used += c, rest -= c;
}
return used;
}
public:
void resize(int _n) {return n = _n, graph.resize(n + 1), cur.resize(n + 1), dist.resize(n + 1);}
void addEdge(int from, int to, int cap){
return graph[from].push_back(Edge{to, (int)graph[to].size(), cap}),
graph[to].push_back(Edge{to, (int)graph[from].size() - 1, 0});
}
int maxflow(int _S, int _T){
S = _S, T = _T;
int ans = 0;
while(bfs()) ans += dfs(S, INF);
return ans;
}
};
int a[55][55];
int main(){
ios::sync_with_stdio(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j){
char ch; cin >> ch;
if(ch == '#') a[i][j] = 1;
}
int base = n * m, S = 2 * base + 1, T = 2 * base + 2;
Dinic dnc;
dnc.resize(T);
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j){
int p = (i - 1) * m + j;
dnc.addEdge(p, base + p, 1);
if(!a[i][j]) continue;
for(int dx = i - 2; dx <= i + 2; ++ dx)
for(int dy = j - 2; dy <= j + 2; ++ dy){
if(dx < 1 || dx > n || dy < 1 || dy > m || !a[dx][dy]) continue;
int q = (dx - 1) * m + dy;
if(p < q) dnc.addEdge(p + base, q, INF), dnc.addEdge(q + base, p, INF);
}
if(i == n || j == 1) dnc.addEdge(S, p, INF);
if(i == 1 || j == m) dnc.addEdge(base + p, T, INF);
}
cout << dnc.maxflow(S, T) << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
input:
4 6 .##... .#.... ##.... ....#.
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3928kb
input:
20 30 ...########################### #..########################### ...########################### ...########################### .############################# ...########################### ...########################### #..########################### ...########################### ..#...............
output:
11
result:
ok 1 number(s): "11"
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 4340kb
input:
35 35 ....###########...#########........ ##..#######################..#####. ....#######################..#####. ...#.....##################..#####. .##......##################.....##. .##..##..#############.....#....##. .....##..#############......##..##. ....#....#############..##..##..##. ####.....
output:
13
result:
wrong answer 1st numbers differ - expected: '16', found: '13'