QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#648459 | #9224. Express Eviction | Arghariza | WA | 1ms | 4280kb | C++14 | 3.5kb | 2024-10-17 19:05:49 | 2024-10-17 19:05:50 |
Judging History
answer
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;
const int inf = 1e9;
struct Flow {
int n, s, t, tot;
struct edge { int to, nxt, w; };
vector<int> hd, cr, d;
vector<edge> e;
Flow () { }
Flow (int _n) : n(_n), tot(-1) { hd.resize(n + 5, -1), d.resize(n + 5, 0), e.clear(); }
void add_edge(int u, int v, int w) { e.eb((edge) { v, hd[u], w }), hd[u] = ++tot; }
void add_flow(int u, int v, int w) { add_edge(u, v, w), add_edge(v, u, 0); }
bool bfs() {
fill(d.begin(), d.end(), 0);
queue<int> q; q.push(s), d[s] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = hd[u]; ~i; i = e[i].nxt) {
int v = e[i].to;
if (!e[i].w || d[v]) continue;
d[v] = d[u] + 1, q.push(v);
}
}
return d[t];
}
int dfs(int u, int in) {
if (u == t) return in;
int out = 0;
for (int &i = cr[u]; ~i; i = e[i].nxt) {
int v = e[i].to;
if (e[i].w && d[v] == d[u] + 1) {
int res = dfs(v, min(in, e[i].w));
in -= res, out += res;
e[i].w -= res, e[i ^ 1].w += res;
}
if (!in) break;
}
if (!out) d[u] = 0;
return out;
}
int dinic() {
FlowBack();
int mf = 0;
while (bfs()) cr = hd, mf += dfs(s, 1e9);
return mf;
}
void FlowBack() {
for (int i = 0; i < tot; i += 2)
e[i].w += e[i ^ 1].w, e[i ^ 1].w = 0;
}
vector<bool> cut() {
queue<int> q; vector<bool> vs;
vs.resize(n + 5, 0), q.push(s), vs[s] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = hd[u]; ~i; i = e[i].nxt) {
int v = e[i].to;
if (!vs[v] && e[i].w && d[v] == d[u] + 1)
vs[v] = 1, q.push(v);
}
}
return vs;
}
vector<tu> cutree(vector<int> S) {
if (S.size() == 1) return vector<tu>();
s = S[0], t = S[1]; int w = dinic();
vector<tu> res; res.eb(mt(s, t, w));
vector<int> sl, sr;
auto vs = cut();
for (int i : S)
if (!vs[i]) sl.eb(i);
else sr.eb(i);
auto tl = cutree(sl), tr = cutree(sr);
for (tu i : tl) res.eb(i);
for (tu i : tr) res.eb(i);
return res;
}
vector<tu> cutree() {
vector<int> S;
for (int i = 1; i <= n; i++) S.eb(i);
s = 1, t = 2;
return cutree(S);
}
};
const int N = 55;
int n, m, ct;
int id[N][N];
char c[N][N];
void solve() {
cin >> n >> m;
F (i, 1, n) {
cin >> (c[i] + 1);
F (j, 1, m)
if (c[i][j] == '#') id[i][j] = ++ct;
}
Flow G(ct * 2 + 2); G.s = ct * 2 + 1, G.t = ct * 2 + 2;
F (i, 1, n) {
F (j, 1, m) {
if (id[i][j]) {
if (j == 1 || i == n) G.add_flow(G.s, id[i][j], 1);
if (i == 1 || j == m) G.add_flow(id[i][j] + ct, G.t, 1);
F (dx, -2, 2) {
F (dy, -2, 2) {
int x = i + dx, y = j + dy;
if (x == i && y == j) continue;
if (x < 1 || y < 1 || x > n || y > m) continue;
if (id[x][y]) G.add_flow(id[i][j], id[x][y] + ct, inf);
}
}
}
}
}
cout << G.dinic() << '\n';
}
bool Med;
int main() {
// FIO("");
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3988kb
input:
4 6 .##... .#.... ##.... ....#.
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 4280kb
input:
20 30 ...########################### #..########################### ...########################### ...########################### .############################# ...########################### ...########################### #..########################### ...########################### ..#...............
output:
3
result:
wrong answer 1st numbers differ - expected: '11', found: '3'