QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94061#5472. Secure the Top Secretwhatever#WA 2ms3584kbC++234.9kb2023-04-05 09:45:232023-04-05 09:45:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-05 09:45:24]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3584kb
  • [2023-04-05 09:45:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 110;
namespace flow {
	constexpr int V = 10010, E = 100010;
	struct edge {
		int to, f, w, nxt;
	}e[E * 2];
	int head[V], cur[V], vis[V];
	int n, s, t, cnt, dis[V], h[V];
	void init(int _n, int _s, int _t) {
		n = _n, s = _s, t = _t, cnt = 1;
	}
	void add(int u, int v, int f, int w) {
		e[++ cnt] = {v, f, w, head[u]}, head[u] = cnt;
		e[++ cnt] = {u, 0, -w, head[v]}, head[v] = cnt;
	}
	bool dij() {
		memcpy(cur, head, n + 1 << 2);
		memset(dis, 0x3f, n + 1 << 2);
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
		dis[s] = 0; q.emplace(0, s);
		while(!q.empty()) {
			auto [d, u] = q.top(); q.pop();
			if(d != dis[u]) continue;
			for(int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to, w = e[i].w + h[u] - h[v];
				if(e[i].f && dis[v] > dis[u] + w) {
					dis[v] = dis[u] + w;
					q.emplace(dis[v], v);
				}
			}
		}
		return dis[t] < dis[0];
	}
	int dfs(int u, int flow) {
		if(u == t) return flow;
		int ret = flow; vis[u] = 1;
		for(int &i = cur[u]; i; i = e[i].nxt) {
			int v = e[i].to, w = e[i].w + h[u] - h[v];
			if(e[i].f && dis[v] == dis[u] + w && !vis[v]) {
				int k = dfs(v, min(e[i].f, ret));
				ret -= k, e[i].f -= k, e[i ^ 1].f += k;
				if(!ret) break;
			}
		}
		vis[u] = 0;
		return flow - ret;
	}
	
	void spfa() {
		static int use[V];
		memset(dis, 0x3f, n + 1 << 2);
		queue<int> q;
		dis[s] = 0; q.emplace(s);
		while(!q.empty()) {
			int u = q.front() ; q.pop(); use[u] = 0;
			for(int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to;
				i64 w = e[i].w;
				if(e[i].f && dis[v] > dis[u] + w) {
					dis[v] = dis[u] + w;
					if(!use[v]) q.emplace(v), use[v] = 1;
				}
			}
		}
	}

	pair<int, int> mincostmaxflow() {
		int flow = 0, cost = 0;
		while(dij()) {
			int ret = dfs(s, INT_MAX);
			for(int i = 0; i <= n; i ++) if(dis[i] < dis[0]) {
				h[i] += dis[i];
			}
			flow += ret;
			cost += ret * h[t];
			if(flow >= 2) break;
		}
		return {flow, cost};
	}
}

int n, m, id[N][N];
int banR[N][N], banC[N][N];
string str[N];
int main() {
	// freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;	
	for(int i = 0; i < n; i ++) {
		cin >> str[i];
		for(int j = 0; j < m; j ++) {
			if(str[i][j] == '#') {
				banR[i][j] = 2;
				banR[i][j + 1] = 2;
				banC[i][j] = 2;
				banC[i + 1][j] = 2;
			}
		}
	}
	int tot = 0;
	for(int i = 0; i <= n; i ++) {
		for(int j = 0; j <= m; j ++) {
			id[i][j] = tot ++;
		}
	}
	int k; cin >> k;
	for(int i = 0; i < k; i ++) {
		int r, c; char o;
		cin >> r >> c >> o;
		r --, c --;
		if(o == 'r') banR[r][c + 1] = 1;
		if(o == 'b') banC[r + 1][c] = 1;
	}

	vector<pair<int, int>> pos;
	for(int i = 0; i < n; i ++) pos.emplace_back(i, 0);
	for(int i = 1; i < m; i ++) pos.emplace_back(n - 1, i);
	for(int i = n - 2; i >= 0; i --) pos.emplace_back(i, m - 1);
	for(int i = m - 2; i > 0; i --) pos.emplace_back(0, i);
	rotate(pos.begin(), find_if(pos.begin(), pos.end(), [&] (auto p) {return str[p.first][p.second] == 'T';}), pos.end());
	auto trans = [&] (int x, int y) -> pair<int, int> {
		if(x == 0 && y == 0) return {x + 1, y};
		if(x == n - 1 && y == 0) return {x + 1, y + 1};
		if(x == n - 1 && y == m - 1) return {x, y + 1};
		if(x == 0 && y == m - 1) return {x, y};
		if(x == 0) return {x, y};
		if(y == 0) return {x + 1, y};
		if(x == n - 1) return {x + 1, y + 1};
		if(y == m - 1) return {x, y + 1};
		assert(false);
	};
	int p, q;
	for(int i = 0; i < pos.size(); i ++) {
		auto [x, y] = pos[i];
		if(str[x][y] == 'S') {
			p = i;
		}
		if(str[x][y] == 'U') {
			q = i;
		}
	}
	flow::init(tot + 1, tot, tot + 1);
	if(p < q) {
		for(int i = p; i < q; i ++) {
			auto [x, y] = trans(pos[i].first, pos[i].second);
			flow::add(flow::s, id[x][y], 1, 0);
		}
		for(int i = q; i < pos.size(); i ++) {
			auto [x, y] = trans(pos[i].first, pos[i].second);
			flow::add(id[x][y], flow::t, 1, 0);
		}
	} else {
		for(int i = q; i < p; i ++) {
			auto [x, y] = trans(pos[i].first, pos[i].second);
			flow::add(flow::s, id[x][y], 1, 0);
		}
		for(int i = 0; i < q; i ++) {
			auto [x, y] = trans(pos[i].first, pos[i].second);
			flow::add(id[x][y], flow::t, 1, 0);
		}
	}

	for(int i = 0; i < n; i ++) {
		for(int j = 0; j <= m; j ++) {
			if(banR[i][j]) {
				flow::add(id[i][j], id[i + 1][j], 1 + (banR[i][j] == 2), banR[i][j] == 1);
				flow::add(id[i + 1][j], id[i][j], 1 + (banR[i][j] == 2), banR[i][j] == 1);
			}
		}
	}
	
	for(int i = 0; i <= n; i ++) {
		for(int j = 0; j < m; j ++) {
			if(banC[i][j]) {
				flow::add(id[i][j], id[i][j + 1], 1 + (banC[i][j] == 2), banC[i][j] == 1);
				flow::add(id[i][j + 1], id[i][j], 1 + (banC[i][j] == 2), banC[i][j] == 1);
			}
		}
	}
	auto [flow, cost] = flow::mincostmaxflow();
	cout << (flow < 2 ? -1 : cost) << '\n';
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3488kb

input:

3 3
S..
#..
U.T
7
1 2 b
1 3 b
2 2 b
2 2 r
2 3 b
3 1 r
3 2 r

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

2 2
ST
.U
4
1 1 r
1 1 b
1 2 b
2 1 r

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

7 10
U.........
..........
###.......
..........
.......###
..........
S........T
18
4 4 r
5 4 r
6 7 r
7 7 r
3 4 b
3 5 b
3 6 b
3 7 b
3 8 b
3 9 b
3 10 b
5 1 b
5 2 b
5 3 b
5 4 b
5 5 b
5 6 b
5 7 b

output:

14

result:

ok single line: '14'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3456kb

input:

2 5
.T.#S
....U
10
1 3 b
1 1 r
1 1 b
2 1 r
1 2 b
1 5 b
2 2 r
1 2 r
2 3 r
2 4 r

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3504kb

input:

5 5
U.S..
.....
.....
.....
.T...
12
2 4 b
4 1 b
2 2 r
1 5 b
2 2 b
4 3 b
5 3 r
1 2 b
3 2 r
2 1 r
3 3 r
2 4 r

output:

-1

result:

ok single line: '-1'

Test #6:

score: -100
Wrong Answer
time: 2ms
memory: 3584kb

input:

5 4
....
...U
....
S#..
.#T.
12
3 4 b
2 1 b
4 3 r
2 2 b
4 3 b
3 3 r
2 3 r
1 1 b
2 2 r
4 4 b
3 1 b
1 3 r

output:

7

result:

wrong answer 1st lines differ - expected: '-1', found: '7'