QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#635525#9412. Stop the CastleFangYifanRE 0ms0kbC++176.9kb2024-10-12 20:03:422024-10-12 20:03:42

Judging History

This is the latest submission verdict.

  • [2024-10-12 20:03:42]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-10-12 20:03:42]
  • 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;
    vector<point> p(n + 1), obs(n + 1);
    cin >> n; for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y;
    cin >> m; 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: 0
Runtime Error

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:


result: