QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94067 | #5472. Secure the Top Secret | whatever# | RE | 7ms | 4848kb | C++23 | 5.9kb | 2023-04-05 10:06:50 | 2023-04-05 10:06:51 |
Judging History
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.#..#.....#..........#..... .................................#.#............................................................... ............#..........#..#..#.........#...................#............................#.......