QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#635571 | #9412. Stop the Castle | FangYifan | WA | 12ms | 3752kb | C++17 | 7.0kb | 2024-10-12 20:11:49 | 2024-10-12 20:11:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
constexpr int mod = 998244353;
constexpr int N = 1e6 + 10;
template <class T>
struct Flow {
T inf;
int n;
struct Edge {
int v;
T cap;
Edge(int v, T cap) : v(v), cap(cap) {}
};
vector<Edge> e; // e[i] 存编号为 i 的边所指向的节点 v / 流量 cap
vector<vector<int>> g; // g[u] 存储了所有以 u 为起点的边 u -> v 的编号 i
vector<int> cur, deep;
Flow(int n) : inf(numeric_limits<T>::max()), n(n), g(n + 1) {}
bool bfs(int s, int t) {
deep.assign(n + 1, -1);
queue<int> q;
deep[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i : g[u]) {
auto [v, c] = e[i];
if (c > 0 && deep[v] == -1) {
deep[v] = deep[u] + 1;
if (v == t) return true;
q.push(v);
}
}
}
return false;
}
T dfs(int u, int t, T flow) {
if (u == t) return flow;
T remain = flow;
for (int &i = cur[u]; i < (int)g[u].size(); i++) {
int j = g[u][i];
auto [v, c] = e[j];
if (c > 0 && deep[v] == deep[u] + 1) {
T cost = dfs(v, t, min(remain, c));
e[j].cap -= cost;
e[j ^ 1].cap += cost;
remain -= cost;
if (remain == 0) return flow;
}
}
return flow - remain;
}
void add(int u, int v, T cap) {
g[u].push_back(e.size());
e.emplace_back(v, cap);
g[v].push_back(e.size());
e.emplace_back(u, 0);
}
// 最大流: 从源点 s 到汇点 t 的最大流量
T max_flow(int s, int t) {
T ans = 0;
while (bfs(s, t)) {
cur.assign(n + 1, 0);
ans += dfs(s, t, inf);
}
return ans;
}
// 最小割: 分割源点 s 到汇点 t 容量和最小的割边集合,最小割 = 最大流
vector<int> min_cut_ST() { // 标记最小割 (S, T)
vector<int> c(n + 1);
for (int i = 1; i <= n; i++) {
c[i] = (deep[i] != -1); // 源点 s 可到达节点 i
}
return c;
}
struct _Edge {
int u, v;
T cap;
T flow;
};
vector<_Edge> edges() {
vector<_Edge> t;
for (int i = 0; i < e.size(); i += 2) {
_Edge x;
x.u = e[i + 1].v;
x.v = e[i].v;
x.cap = e[i].cap + e[i + 1].cap;
x.flow = e[i + 1].cap;
t.push_back(x);
}
return t;
}
};
struct point { int x, y; };
void solve() {
int n, m;
cin >> n;
vector<point> p(n + 1);
for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y;
cin >> m;
vector<point> obs(m + 1);
for (int i = 1; i <= m; i++) cin >> obs[i].x >> obs[i].y;
// 两车相邻,判断无解
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (p[i].x == p[j].x && abs(p[i].y - p[j].y) == 1) {
cout << "-1\n";
return;
} else if (p[i].y == p[j].y && abs(p[i].x - p[j].x) == 1) {
cout << "-1\n";
return;
}
}
}
// 每一行 / 每一列 维护坐标
map<int, vector<pair<int, int>>> r, c;
for (int i = 1; i <= n; i++) {
r[p[i].x].push_back({p[i].y, 1});
c[p[i].y].push_back({p[i].x, 1});
}
for (int i = 1; i <= m; i++) {
r[obs[i].x].push_back({obs[i].y, 2});
c[obs[i].y].push_back({obs[i].x, 2});
}
for (auto &[x, y] : r) sort(y.begin(), y.end());
for (auto &[x, y] : c) sort(y.begin(), y.end());
// 离散化坐标 -> 实际坐标
int numr = r.size(), numc = c.size();
vector<int> X(numr + 1), Y(numc + 1);
auto it = r.begin();
for (auto i = 1; i <= numr; i++, it++) X[i] = it->first;
it = c.begin();
for (auto i = 1; i <= numc; i++, it++) Y[i] = it->first;
// 对于行列碰撞的交点 (x, y),建立 x -> y 的有向边,容量为 1,那么求最大流即可
Flow<int> f(numr + numc + 2);
int S = numr + numc + 1, T = numr + numc + 2;
for (int i = 1; i <= numr; i++) f.add(S, i, 1);
for (int i = 1; i <= numc; i++) f.add(numr + i, T, 1);
map<pair<int, int>, array<pair<int, int>, 4>> insect;
for (int i = 1; i <= numr; i++) {
for (int j = 1; j <= numc; j++) {
int x = X[i], y = Y[j];
if (!r.count(x) || !c.count(y)) continue;
auto r2 = lower_bound(r[x].begin(), r[x].end(), make_pair(y, 0));
auto c2 = lower_bound(c[y].begin(), c[y].end(), make_pair(x, 0));
auto r1 = r2, c1 = c2;
if (r1 == r[x].begin() || c1 == c[y].begin()) continue;
r1--; c1--;
if (r1->first < y && r1->second == 1 && r2->first > y && r2->second == 1) {
if (c1->first < x && c1->second == 1 && c2->first > x && c2->second == 1) {
// cerr << "add: " << x << ' ' << y << "\n";
insect[{i, j}] = {make_pair(x, r1->first), make_pair(x, r2->first), make_pair(c1->first, y), make_pair(c2->first, y)};
f.add(i, numr + j, 1);
}
}
}
}
// 处理碰撞点对 and 对应的放置方案
set<pair<int, int>> st;
vector<pair<int, int>> ans;
f.max_flow(S, T);
auto e = f.edges();
for (auto [u, v, cap, flow] : e) {
if (u == S || v == T) continue;
if (flow == 1) {
v -= numr;
// cerr << "flow: " << X[u] << ' ' << Y[v] << "\n";
ans.emplace_back(X[u], Y[v]);
for (auto x : insect[{u, v}]) {
// cerr << "ban: " << x.first << ' ' << x.second << "\n";
st.insert(x);
}
}
}
for (auto [x, v] : r) {
for (int j = 1; j < v.size(); j++) {
if (v[j - 1].second == 1 && v[j].second == 1) {
int y1 = v[j - 1].first, y2 = v[j].first;
if (st.count({x, y1}) && st.count({x, y2})) continue;
ans.emplace_back(x, y1 + 1);
}
}
}
for (auto [y, v] : c) {
for (int j = 1; j < v.size(); j++) {
if (v[j - 1].second == 1 && v[j].second == 1) {
int x1 = v[j - 1].first, x2 = v[j].first;
if (st.count({x1, y}) && st.count({x2, y})) continue;
ans.emplace_back(x1 + 1, y);
}
}
}
cout << ans.size() << "\n";
for (auto [x, y] : ans) cout << x << ' ' << y << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
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: 0
Accepted
time: 2ms
memory: 3604kb
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 34 18 29 38 5 16 10 16 15 12 6 20 26 34 50 0 1 16 10 0 1 43 22 5 1 3 1 13 33 10 44 45 42 44 0 5 27 41 29 26 44 4 8 1 21 15 1 32 9 0 0 0 0 6 23 10 35 34 12 11 23 44 29 21 24 46 0 3 20 30 43 25 31 17 0 -1 3 16 36 25 7 17 39 6 5 5 8 9 6 4 7 3 3 10 2 11
result:
ok ok 21 cases (21 test cases)
Test #3:
score: -100
Wrong Answer
time: 12ms
memory: 3752kb
input:
2 200 7 52 9 160 10 4 12 61 18 436 19 430 20 499 24 139 25 416 29 53 33 153 35 275 35 310 37 25 38 477 39 349 42 120 44 158 45 330 49 486 50 204 51 67 52 138 52 305 56 139 63 132 66 4 67 327 70 484 71 67 72 308 74 218 76 479 81 139 82 90 86 201 87 335 91 35 91 220 92 496 94 29 94 436 96 359 97 299 1...
output:
43 52 139 91 61 94 160 126 67 132 138 154 496 185 147 187 467 199 432 224 35 260 275 270 305 277 356 306 374 311 177 334 186 349 112 352 153 393 307 35 276 126 214 154 117 261 468 274 67 277 189 311 455 390 308 440 179 453 251 11 4 38 25 312 61 52 67 57 139 278 272 415 305 286 367 307 367 380 385 13...
result:
wrong answer There are still 4 pairs of castles which can attack each other (test case 1)