QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#635571#9412. Stop the CastleFangYifanWA 12ms3752kbC++177.0kb2024-10-12 20:11:492024-10-12 20:11:49

Judging History

This is the latest submission verdict.

  • [2024-10-12 20:11:49]
  • Judged
  • Verdict: WA
  • Time: 12ms
  • Memory: 3752kb
  • [2024-10-12 20:11:49]
  • Submitted

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)