QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648459#9224. Express EvictionArgharizaWA 1ms4280kbC++143.5kb2024-10-17 19:05:492024-10-17 19:05:50

Judging History

你现在查看的是最新测评结果

  • [2024-10-17 19:05:50]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4280kb
  • [2024-10-17 19:05:49]
  • 提交

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'