QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94067#5472. Secure the Top Secretwhatever#RE 7ms4848kbC++235.9kb2023-04-05 10:06:502023-04-05 10:06:51

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 10:06:51]
  • 评测
  • 测评结果:RE
  • 用时:7ms
  • 内存:4848kb
  • [2023-04-05 10:06:50]
  • 提交

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];
int bad[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);
	auto bfs = [&] (int x, int y) {
		static int vis[N][N];
		queue<pair<int, int>> q;
		q.emplace(x, y); vis[x][y] = 1;
		while(!q.empty()) {
			auto [x, y] = q.front(); q.pop();
			bad[x][y] =1;
			bad[x + 1][y] = 1;
			bad[x][y + 1] = 1;
			bad[x + 1][y + 1] = 1;
			for(auto dir : {array<int, 2> {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}}) {
				int dx = x + dir[0], dy = y + dir[1];
				if(dx >= 0 && dx < n && dy >= 0 && dy < m && str[dx][dy] == '#' && !vis[dx][dy]) {
					q.emplace(dx, dy);
					vis[dx][dy] = 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);
		}
		for(int i = 0; i < p; i ++) {
			auto [x, y] = pos[i];
			if(str[x][y] == '#') {
				bfs(x, y);
			} else {
				tie(x, y) = trans(x, y);
				bad[x][y] = 1;
			}
		}
	} 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 = p; i < pos.size(); i ++) {
			auto [x, y] = pos[i];
			if(str[x][y] == '#') {
				bfs(x, y);
			} else {
				tie(x, y) = trans(x, y);
				bad[x][y] = 1;
			}
		}
	}

	for(int i = 0; i < n; i ++) {
		for(int j = 0; j <= m; j ++) {
			if(banR[i][j] && !bad[i][j] && !bad[i + 1][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] && !bad[i][j] && !bad[i][j + 1]) {
				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: 0ms
memory: 3548kb

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: 3468kb

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: 3536kb

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: 1ms
memory: 3472kb

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: 3472kb

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: 0
Accepted
time: 0ms
memory: 3524kb

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:

-1

result:

ok single line: '-1'

Test #7:

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

input:

3 3
UST
###
.#.
2
1 1 r
1 2 r

output:

-1

result:

ok single line: '-1'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

4 2
U.
..
.T
S.
8
1 1 b
3 1 r
4 1 r
1 1 r
2 2 b
3 2 b
3 1 b
2 1 r

output:

5

result:

ok single line: '5'

Test #9:

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

input:

2 2
S.
UT
4
1 1 b
1 2 b
2 1 r
1 1 r

output:

-1

result:

ok single line: '-1'

Test #10:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #11:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #12:

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

input:

4 4
.T.S
#.#.
....
U...
6
3 1 b
1 4 b
2 4 b
3 2 b
4 1 r
3 2 r

output:

-1

result:

ok single line: '-1'

Test #13:

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

input:

5 5
.##T.
##.#.
.#...
##.##
#SU..
6
2 3 b
3 3 r
4 3 b
1 5 b
3 4 r
5 4 r

output:

-1

result:

ok single line: '-1'

Test #14:

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

input:

97 97
S...............................................................................................T
.................................................................................................
.................................................................................................
...

output:

130

result:

ok single line: '130'

Test #15:

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

input:

100 94
S............................................................................................T
..............................................................................................
..............................................................................................
...........

output:

126

result:

ok single line: '126'

Test #16:

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

input:

95 92
S..........................................................................................T
............................................................................................
............................................................................................
..................

output:

124

result:

ok single line: '124'

Test #17:

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

input:

92 92
S..........................................................................................T
............................................................................................
............................................................................................
..................

output:

124

result:

ok single line: '124'

Test #18:

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

input:

96 100
S..................................................................................................T
....................................................................................................
..............................................................................................

output:

134

result:

ok single line: '134'

Test #19:

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

input:

92 90
S........................................................................................T
..........................................................................................
..........................................................................................
........................

output:

120

result:

ok single line: '120'

Test #20:

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

input:

96 90
S........................................................................................T
..........................................................................................
..........................................................................................
........................

output:

120

result:

ok single line: '120'

Test #21:

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

input:

92 94
S............................................................................................T
..............................................................................................
..............................................................................................
............

output:

126

result:

ok single line: '126'

Test #22:

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

input:

99 94
S............................................................................................T
..............................................................................................
..............................................................................................
............

output:

126

result:

ok single line: '126'

Test #23:

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

input:

93 91
S.........................................................................................T
...........................................................................................
...........................................................................................
.....................

output:

122

result:

ok single line: '122'

Test #24:

score: 0
Accepted
time: 4ms
memory: 4184kb

input:

50 83
........................#.............................#........#......#.....#......
...........................................#........#................#........#....
....................#.....#........................................................
................................#............

output:

22

result:

ok single line: '22'

Test #25:

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

input:

58 98
.........#.....#...U............#..............#.......#....................##...........#........
.........#........#.....#...#..#........#.#.........#..................#.#........................
.#.##.......#........#......#..#.....#.........#..#.........#...##.........###..##......#..........

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0
Accepted
time: 3ms
memory: 4236kb

input:

80 48
..##.#.........#...#.....#............#.#.#.#...
....#........#.......#...#.##.#.##....#.##.#...#
#......##.#..#.......#.....##..#..#.......##.#.#
.##.#...#.#.#.#.....###...#......#............##
.....#.#.....#.#..##.......##..#...#.#..#..##...
.......#....#.#...##.##.##....#...#......#..####
...

output:

2

result:

ok single line: '2'

Test #27:

score: 0
Accepted
time: 3ms
memory: 3824kb

input:

40 49
#.....................#..................#.......
..................#......#....#..#....#.#.......U
......#.................................#........
.................................................
#.......#.......#..........#.....................
....#.......#.......#............#.............

output:

9

result:

ok single line: '9'

Test #28:

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

input:

25 39
.......................#...............
...................................#...
.......................................
##.......................#.............
..................#.........#..........
..#...................................U
...............................#.......
.................

output:

-1

result:

ok single line: '-1'

Test #29:

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

input:

17 47
..#.....#...#...#........................T.#...
.........................#.........#......#....
.....#..........##..#.......#...#........#.....
......#.......................#................
##...#........#.......##.#.#.......#.##........
...............................................
#..#.....

output:

-1

result:

ok single line: '-1'

Test #30:

score: 0
Accepted
time: 3ms
memory: 3636kb

input:

18 66
...#..#...#..#.#...#U#.#....##...#.#.#.......#.#..........#......#
....##...#...##..##.....#..#.##.#..##...........#....#.....#...#.#
#...##..........##.....#........#...##.#.##............#.#...#.#..
#.#..#..#........#..#....#...#..#.....##..#..#..............#....#
.........#...##.#..#.#.###...

output:

4

result:

ok single line: '4'

Test #31:

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

input:

69 81
.....#..........#.##..U....#..#.S#....#..###..##...........#....##..####.#T.##.##
##........##...##.#.#.##...#.###.#...#....##..#...#..###.....#.................#.
.......##...###..#....#..###.....#..##...#....#..#..#...#.#...#.#....#...##...#.#
#...#...........##..###.#.#.##.#...#.#....#..#.#...

output:

2

result:

ok single line: '2'

Test #32:

score: 0
Accepted
time: 3ms
memory: 3960kb

input:

87 26
.##....#.U.#.#.#......#...
...#...##..#...#.##...#..T
#..........#...#.....#.#..
##.#..##...##.#..#..#.....
................##.....##.
......###..##.#..#..#.....
...#.....#....##..#.......
#.......###..#.....#......
######..##......#.....#...
#.#.#....#.#.........#..#.
.#.....#..###..#......#....

output:

4

result:

ok single line: '4'

Test #33:

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

input:

19 92
.#....#.#.....#.#.........###..S##.#...#..#.#..#...#..####.......#.......#...#.##.##...##...
.......#.#.#.#..#...#..###..#...#..#....#......##........#.#.........#..#.###....#.....#....
......#...#..#.#...#.....##..##......##.###....#...#....#.#.###..#...#####.##..#....#..#.###
.##...##.#.#..#...

output:

2

result:

ok single line: '2'

Test #34:

score: 0
Accepted
time: 1ms
memory: 4392kb

input:

92 96
...#..##.#..##.......#.....#..#.#S#....#.........##...#.#..#...#.......#..#............#..#..#..
...#.#.#.#....#.##....#....#.#....#...#...#....#..##....#..#....#...#..#....#....##....#..#.....
.#...#..#.........#..........#.##.#..#..#.#..#..#.....#.#....#.#.#..........##.......#.#....##..
......

output:

-1

result:

ok single line: '-1'

Test #35:

score: 0
Accepted
time: 7ms
memory: 4824kb

input:

90 90
##....#........#..#..#.#...#...#.#....#.#....##..#.#......#...#......T.#..####........#.#.
..#...............#.#...#...#......#.......#.#..#.#.......#...#.....##....#..##.....#.....
.###.......##.##.........#.#.#..##.##..#........#.#......#......#.#.#..###..##..#.#.....#.
..##......#.........#...

output:

6

result:

ok single line: '6'

Test #36:

score: 0
Accepted
time: 3ms
memory: 4448kb

input:

98 93
..#...........##..........##.#......#....#.....#.......#..#.#.#.......#..................U.#.
..#........#..#..#...#...##.................#.#........#.......##.#..#..#.....#.......#.###.#
...........###..#####.#..##.......#.#........#.#.....#.......#......#....#..#..#.............
#...#.#........

output:

-1

result:

ok single line: '-1'

Test #37:

score: 0
Accepted
time: 1ms
memory: 4416kb

input:

96 97
#............#.................#....#.#.#...#....#..###..#.#....#.##...#..#...........#..........
..#.........##........#...#.##....##....###...#.###..#.#..............##.#.....................#.
..#..........#.#.#..#...........#...##............#......##...................#......##....#.....
...

output:

-1

result:

ok single line: '-1'

Test #38:

score: 0
Accepted
time: 5ms
memory: 4848kb

input:

91 94
#...........#.#.##.#..#.....#.#........S.##.......##....#..#........#..#...#..#..#........#U#.
...#.....#..#.....##.#..#.##....#...#.##....#....#......##.#.#............##.......#....#....#
#..#...#..#...#.#..###.#...#....#..##....#....##....#.#.##.........#..#...#.#........#.#.#..##
....##......

output:

4

result:

ok single line: '4'

Test #39:

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

input:

94 91
...........#......#...#.....#..###.....#.......#....##.#....#........#......####.......#...
..#...###...##.......#..#....#..#.###.#....#......#.#..####.##...#...#..##..#.#...###..#...
..#.#.##..#...........#.........#.#.......#...........#.###......#..#....#......#...#......
.#.....##..#.....#...

output:

21

result:

ok single line: '21'

Test #40:

score: 0
Accepted
time: 6ms
memory: 4592kb

input:

90 94
##..........#.#.#.....#.....#..#..#......#.#..##..##....##..#.#.#..#.###.#...#.........T.#....
....#.#.....#.#...............##..#..##.##.#..#....##....###.#.#.#...#..###.........#.##....##
...##.............#..#.....#..#..#.......#....#...###....#.#..#...#.#....#...###..####........
#..##...#...

output:

24

result:

ok single line: '24'

Test #41:

score: 0
Accepted
time: 3ms
memory: 4192kb

input:

93 98
.............#.........#.....U..#......................##.........................................
...........#............#...........................................................###...#.......
....................................................................................#..............

output:

-1

result:

ok single line: '-1'

Test #42:

score: 0
Accepted
time: 6ms
memory: 4656kb

input:

96 100
..........#........#..#...#..#.........#....#....#.#.....##......##....##............#.............#
.......#.#..#.#.#..#....................#..............##.....#.........#...#...#.....#.....#.....#.
##.....##.#.###...#...#.#.............###.#.......#.#................#........#........##.....

output:

12

result:

ok single line: '12'

Test #43:

score: -100
Dangerous Syscalls

input:

100 99
................#..#............T.....#.....#.....#............#.#.....U.#..#.....#..........#.....
.................................#.#...............................................................
............#..........#..#..#.........#...................#............................#.......

output:


result: