QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94061 | #5472. Secure the Top Secret | whatever# | WA | 2ms | 3584kb | C++23 | 4.9kb | 2023-04-05 09:45:23 | 2023-04-05 09:45:24 |
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];
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'