QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#682712#9412. Stop the CastleyangylWA 0ms3620kbC++206.0kb2024-10-27 17:03:182024-10-27 17:03:28

Judging History

This is the latest submission verdict.

  • [2024-10-27 17:03:28]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3620kb
  • [2024-10-27 17:03:18]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
using ll = long long;
template<class T>
struct MaxFlow {
    struct Edge {
        int v;
        T c;
        Edge(int _v, T _c) : v(_v), c(_c) {}
    }; 
    int n;
    vector<Edge> e;
    vector<vector<int>> g;
    vector<int> cur, h;
    
    MaxFlow() {}
    MaxFlow(int n) {
        init(n);
    } 
    void init(int n) {
        this->n = n;
        e.clear();
        g.assign(n, {});
        cur.resize(n);
        h.resize(n);
    }
    void addEdge(int u, int v, T c) {
        g[u].push_back(e.size());
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
    }
    
    bool bfs(int s, int t) {
        h.assign(n, -1);
        queue<int> que;
        h[s] = 0;
        que.push(s);
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            for (int i : g[u]) {
                auto [v, c] = e[i];
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    if (v == t) {
                        return true;
                    }
                    que.push(v);
                }
            }
        }
        return false;
    }   
    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        auto r = f;
        for (int &i = cur[u]; i < int(g[u].size()); ++i) {
            const int j = g[u][i];
            auto [v, c] = e[j];
            if (c > 0 && h[v] == h[u] + 1) {
                auto x = dfs(v, t, min(r, c));
                e[j].c -= x;
                e[j ^ 1].c += x;
                r -= x;
                if (r == 0) {
                    return f;
                }
            }
        }
        return f - r;
    }
    T flow(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, numeric_limits<T>::max());
        }
        return ans;
    }
    
    vector<bool> minCut() {
        vector<bool> c(n);
        for (int i = 0; i < n; i++) {
            c[i] = (h[i] != -1);
        }
        return c;
    }
};
constexpr int INF = numeric_limits<int>::max();

void solve() {
    int n;
    cin >> n;
    vector<int> r(n), c(n);
    for (int i = 0; i < n; i++) {
        cin >> r[i] >> c[i];
    }
    int m;
    cin >> m;
    vector<int> br(m), bc(m);
    for (int i = 0; i < m; i++) {
        cin >> br[i] >> bc[i];
    }

    vector<int> ord1(n), ord2(n);
    iota(ord1.begin(), ord1.end(), 0);
    iota(ord2.begin(), ord2.end(), 0);
    sort(ord1.begin(), ord1.end(), [&](int i, int j) {
        if (r[i] == r[j]) {
            return c[i] < c[j];
        }
        return r[i] < r[j];
    });
    sort(ord2.begin(), ord2.end(), [&](int i, int j) {
        if (c[i] == c[j]) {
            return r[i] < c[j];
        }
        return c[i] < c[j];
    });

    vector<pair<int, int>> row, col;
    for (int o = 0; o < ord1.size() - 1; o++) {
        int i = ord1[o], j = ord1[o + 1];
        if (r[i] != r[j]) continue;
        bool ok = true;
        for (int k = 0; k < m; k++) {
            if (br[k] == r[i] && bc[k] > c[i] && bc[k] < c[j]) {
                ok = false;
            }
        }
        if (ok) {
            row.push_back(pair(i, j));
        }
    }
    for (int o = 0; o < ord2.size() - 1; o++) {
        int i = ord2[o], j = ord2[o + 1];
        if (c[i] != c[j]) continue;
        bool ok = true;
        for (int k = 0; k < m; k++) {
            if (bc[k] == c[i] && br[k] > r[i] && br[k] < r[j]) {
                ok = false;
            }
        }
        if (ok) {
            col.push_back(pair(i, j));
        }
    }


    int N = row.size(), M = col.size();
    vector p(N, vector<pair<int, int>>(M));
    int S = 0, T = N + M + 1;
    MaxFlow<int> g(T + 1);
    for (int i = 0; i < row.size(); i++) {
        g.addEdge(S, i + 1, 1);
        auto [i1, i2] = row[i];
        assert(r[i1] == r[i2]);
        for (int j = 0; j < col.size(); j++) {
            auto [j1, j2] = col[j];
            assert(c[j1] == c[j2]);
            if (c[j1] > min(c[i1], c[i2]) && c[j1] < max(c[i1], c[i2])) {
                p[i][j] = pair(r[i1], c[j1]);
                g.addEdge(i + 1, j + N + 1, 1);
            }
        }  
    }
    for (int i = 0; i < col.size(); i++) {
        g.addEdge(i + N + 1, T, 1);
    }

    g.flow(S, T);
    vector<pair<int, int>> ans;
    auto dfs = [&](auto &&self, int u) -> void {
        if (u > N) return;
        for(int i : g.g[u]) {
            auto [v, c] = g.e[i];
            if (c == 0) {
                self(self, v);
            }
            if (u != 0 && c == 0) {
                ans.push_back(p[u - 1][v - N - 1]);
            }
        }
    };
    dfs(dfs, S);

    vector<int> t;
    for (int i : g.g[S]) {
        auto [v, c] = g.e[i];
        if (c != 0) {
            t.push_back(v);
        }
    }
    for (int i : g.g[T]) {
        auto [v, c] = g.e[i];
        if (c == 0) {
            t.push_back(v);
        }
    }

    for (auto x : t) {
        if (x <= N) {
            auto [i1, i2] = row[x - 1];
            if (abs(c[i1] - c[i2]) == 1) {
                cout << -1 << endl;
                return;
            }
            int x = (c[i1] < c[i2]) ? i1 : i2;
            ans.push_back(pair(r[x], c[x] + 1));
        } else if (x > N) {
            auto [i1, i2] = col[x - N - 1];
            if (abs(r[i1] - r[i2]) == 1) {
                cout << -1 << endl;
                return;
            }
            int x = (r[i1] < r[i2]) ? i1 : i2;
            ans.push_back(pair(r[x] + 1, c[x]));
        }
    }
    cout << ans.size() << endl;
    for (auto [x, y] : ans){
        cout << x << " " << y << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

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: 0ms
memory: 3616kb

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
4
16 26
16 10
12 6
34 50
0
1
16 10
0
1
43 22
4
33 44
1 3
1 13
44 45
0
4
44 15
27 41
29 26
8 1
1
32 9
0
0
0
0
6
12 34
23 10
23 44
29 21
35 5
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:

wrong answer There are still 1 pairs of castles which can attack each other (test case 2)