QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#610428 | #9412. Stop the Castle | UESTC_OldEastWest | WA | 1ms | 3824kb | C++17 | 7.2kb | 2024-10-04 15:55:03 | 2024-10-04 15:55:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
namespace Dinic {
int n, s, t, tot;
std::vector<int> to, nxt, cap, head;
std::vector<int> cur, dep;
void AddEdge(int u, int v, int c) {
to[tot] = v, nxt[tot] = head[u], cap[tot] = c, head[u] = tot++;
}
void Init(int _n, int _s, int _t, std::vector<std::array<int, 3> > &edge) {
n = _n, s = _s, t = _t, tot = 0;
int m = edge.size();
to = nxt = cap = std::vector<int>(m << 1);
head = cur = dep = std::vector<int>(n, -1);
for (auto [u, v, c] : edge) {
AddEdge(u, v, c);
AddEdge(v, u, 0);
}
}
bool BFS() {
dep = std::vector<int>(n, -1);
std::vector<int> que(1, s);
dep[s] = 0;
for (int h = 0, u; h < que.size(); ++h) {
u = que[h];
for (int i = head[u], v, c; ~i; i = nxt[i]) {
v = to[i], c = cap[i];
if (dep[v] == -1 && c) dep[v] = dep[u] + 1, que.emplace_back(v);
}
}
return dep[t] != -1;
}
int DFS (int u, int in) {
if (u == t || !in) return in;
int out = 0;
for (int i = cur[u], v, c; ~i; i = nxt[i]) {
cur[u] = nxt[i];
v = to[i], c = cap[i];
if (c && dep[v] == dep[u] + 1) {
int ret = DFS(v, std::min(in, c));
in -= ret, out += ret;
cap[i] -= ret, cap[i ^ 1] += ret;
}
}
return out;
}
int getMaxFlow() {
int ans = 0;
while (BFS()) {
cur = head;
ans += DFS(s, INT_MAX);
}
return ans;
}
}
void charming() {
int n; std::cin >> n;
std::vector<std::pair<int, int> > castle;
for (int i = 0, r, c; i < n; ++i) {
std::cin >> r >> c;
castle.emplace_back(std::make_pair(r, c));
}
int m; std::cin >> m;
std::vector<std::pair<int, int> > obstacle;
for (int i = 0, r, c; i < m; ++i) {
std::cin >> r >> c;
obstacle.emplace_back(std::make_pair(r, c));
}
std::function<bool(int, int, int)> Check = [&](int x, int y, int z) {
if (x > y) std::swap(x, y);
if (z > x && z < y) return true;
else return false;
};
std::function<bool(int, int, int, int)> hinder = [&](int idx0, int idx1, int idx2, int type) {
bool r_same = castle[idx0].first == castle[idx1].first;
if (type == 0) {
if (r_same) {
if (castle[idx2].first != castle[idx0].first) return false;
int c0 = castle[idx0].second, c1 = castle[idx1].second, c2 = castle[idx2].second;
return Check(c0, c1, c2);
}
else {
if (castle[idx2].second != castle[idx0].second) return false;
int r0 = castle[idx0].first, r1 = castle[idx1].first, r2 = castle[idx2].first;
return Check(r0, r1, r2);
}
}
else {
if (r_same) {
if (obstacle[idx2].first != castle[idx0].first) return false;
int c0 = castle[idx0].second, c1 = castle[idx1].second, c2 = obstacle[idx2].second;
return Check(c0, c1, c2);
}
else {
if (obstacle[idx2].second != castle[idx0].second) return false;
int r0 = castle[idx0].first, r1 = castle[idx1].first, r2 = obstacle[idx2].first;
return Check(r0, r1, r2);
}
}
};
std::function<bool(int, int)> fight = [&](int idx0, int idx1) {
if (castle[idx0].first == castle[idx1].first ||
castle[idx0].second == castle[idx1].second) {
for (int i = 0; i < n; ++i) if (i != idx0 && i != idx1) {
if (hinder(idx0, idx1, i, 0)) return false;
}
for (int i = 0; i < m; ++i) {
if (hinder(idx0, idx1, i, 1)) return false;
}
return true;
}
else return false;
};
bool near = false;
std::vector<std::pair<int, int> > conf_row, conf_col;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (abs(castle[i].first - castle[j].first) +
abs(castle[i].second - castle[j].second) <= 1) {
near = true; break;
}
if (castle[i].first == castle[j].first) {
if (fight(i, j)) conf_row.emplace_back(std::make_pair(i, j));
}
else {
if (fight(i, j)) conf_col.emplace_back(std::make_pair(i, j));
}
}
if (near) break;
}
if (near) {std::cout << -1 << '\n'; return;}
int s = 0, t = 1, tot = 2;
std::map<int, int> mp0, mp1, rev_mp0, rev_mp1;
std::vector<std::array<int, 3> > edge;
int conf_row_cnt = conf_row.size(), conf_col_cnt = conf_col.size();
for (int i = 0; i < conf_row_cnt; ++i) {
mp0[i] = tot, rev_mp0[tot++] = i;
edge.emplace_back((std::array<int, 3>) {s, mp0[i], 1});
}
for (int i = 0; i < conf_col_cnt; ++i) {
mp1[i] = tot, rev_mp1[tot++] = i;
edge.emplace_back((std::array<int, 3>) {mp1[i], t, 1});
}
std::function<bool(int, int)> is_inter = [&](int idx0, int idx1) {
int r0 = conf_row[idx0].first, r1 = conf_row[idx0].second;
int c0 = conf_col[idx1].first, c1 = conf_col[idx1].second;
int r = castle[r1].first, c = castle[c1].second;
if (r <= std::min(castle[c0].first, castle[c1].first)) return false;
if (r >= std::max(castle[c0].first, castle[c1].first)) return false;
if (c <= std::min(castle[r0].second, castle[r1].second)) return false;
if (c >= std::max(castle[r0].second, castle[r1].second)) return false;
return true;
};
std::function<std::pair<int, int>(int, int)> get_inter = [&](int idx0, int idx1) {
int r = castle[conf_row[idx0].first].first, c = castle[conf_col[idx1].first].second;
return std::make_pair(r, c);
};
for (int i = 0; i < conf_row_cnt; ++i) {
for (int j = 0; j < conf_col_cnt; ++j) {
if (is_inter(i, j)) edge.emplace_back((std::array<int, 3>) {mp0[i], mp1[j], 1});
}
}
Dinic::Init(tot, s, t, edge);
int ans = conf_row_cnt + conf_col_cnt - Dinic::getMaxFlow();
std::set<std::pair<int, int> > pos;
{
using namespace Dinic;
std::vector<int> vis_r(conf_row_cnt), vis_c(conf_col_cnt);
for (int u = 0; u < conf_row_cnt; ++u) {
for (int i = head[mp0[u]], v, c; ~i; i = nxt[i]) if (i & 1 ^ 1) {
v = rev_mp1[to[i]], c = cap[i];
if (!c) pos.insert(get_inter(u, v));
vis_r[u] = 1, vis_c[v] = 1;
}
}
for (int i = 0; i < conf_row_cnt; ++i) if (!vis_r[i]) {
auto [idx0, idx1] = conf_row[i];
int r = castle[idx0].first;
int mn = castle[idx0].second, mx = castle[idx1].second;
if (mn > mx) std::swap(mn, mx);
for (int j = mn + 1; j < mx; ++j) {
std::pair<int, int> new_pos = std::make_pair(r, j);
if (pos.count(new_pos)) continue;
else {pos.insert(new_pos); break;}
}
}
for (int i = 0; i < conf_col_cnt; ++i) if (!vis_c[i]) {
auto [idx0, idx1] = conf_col[i];
int c = castle[idx0].second;
int mn = castle[idx0].first, mx = castle[idx1].first;
if (mn > mx) std::swap(mn, mx);
for (int j = mn + 1; j < mx; ++j) {
std::pair<int, int> new_pos = std::make_pair(j, c);
if (pos.count(new_pos)) continue;
else {pos.insert(new_pos); break;}
}
}
}
std::cout << ans << '\n';
for (auto [r, c] : pos) std::cout << r << ' ' << c << '\n';
}
signed main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
int t; std::cin >> t;
while (t--) charming();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3824kb
input:
4 7 1 3 6 6 4 7 2 1 6 3 4 1 2 6 3 3 4 6 4 3 1 2 1 1 2 2 0 3 1 1 1 3 3 3 1 1 2 3 1 1 1 3 2 3 0
output:
2 2 3 4 6 0 1 2 3 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3608kb
input:
21 11 3 5 18 6 19 12 27 48 28 38 30 12 33 18 42 18 43 38 45 46 48 34 3 2 6 24 4 41 45 15 11 6 15 27 16 9 16 14 16 48 19 26 25 12 27 26 28 4 31 40 32 6 33 50 37 50 46 11 50 29 17 1 49 4 9 9 15 9 22 11 31 11 46 14 28 17 5 17 49 18 43 20 31 30 46 33 11 33 33 34 15 36 6 47 10 2 16 46 36 30 11 7 34 7 41 ...
output:
3 20 12 29 38 34 18 5 12 6 16 10 16 15 20 26 34 50 0 1 16 10 0 1 43 22 5 1 3 1 13 33 10 42 44 44 45 0 5 8 1 21 15 27 41 29 26 44 4 1 32 9 0 0 0 0 6 12 11 23 10 23 44 24 46 29 21 35 34 0 3 20 30 31 17 43 25 0 -1 3 16 36 17 39 25 7 6 7 5 8 11
result:
wrong output format Unexpected end of file - int32 expected (test case 21)