QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#634768#9412. Stop the Castleji_114514WA 1ms7932kbC++204.2kb2024-10-12 18:02:562024-10-12 18:03:04

Judging History

This is the latest submission verdict.

  • [2024-10-12 18:03:04]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 7932kb
  • [2024-10-12 18:02:56]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3 + 10, M = 1e6 + 10;
int h[N], e[M], ne[M], w[M], idx = 2;
int n, m, s, t, d[N], cur[N];
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
    e[idx] = a, ne[idx] = h[b], w[idx] = 0, h[b] = idx++;
}

bool bfs()
{
    memset(d, 0, sizeof d);
    queue<int>q;
    q.push(s), d[s] = 1;
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (int i = h[u]; i; i = ne[i])
        {
            int v = e[i];
            if (d[v] == 0 && w[i])
            {
                d[v] = d[u] + 1;
                q.push(v);
                if (v == t)return 1;
            }
        }
    }
    return 0;
}

ll dfs(int u, ll mf)
{
    if (u == t)return mf;
    ll sum = 0;
    for (int i = cur[u]; i; i = ne[i])
    {
        cur[u] = i;
        int v = e[i];
        if (d[v] == d[u] + 1 && w[i])
        {
            ll f = dfs(v, min(mf, 1ll * w[i]));
            sum += f;
            mf -= f;
            w[i] -= f;
            w[i ^ 1] += f;
            if (mf == 0)break;
        }
    }
    if (sum == 0)d[u] = 0;
    return sum;
}

int r[N], c[N];
bool vis[N];

void solve()
{
    cin >> n;
    map<int, vector<int>>hr, hc;
    for (int i = 1; i <= n; i++)cin >> r[i] >> c[i], hr[r[i]].push_back(c[i]), hc[c[i]].push_back(r[i]);
    vector<array<int, 3>>rn, cn;
    cin >> m;
    while (m--)
    {
        int r, c; cin >> r >> c;
        hr[r].push_back(c), hc[c].push_back(r);
    }
    for (auto& [v, k] : hr)sort(k.begin(), k.end());
    for (auto& [v, k] : hc)sort(k.begin(), k.end());
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (r[i] == r[j]) {
                if (abs(c[i] - c[j]) == 1) {
                    cout << -1 << '\n';
                    return;
                }
                auto& v = hr[r[i]];
                auto it = upper_bound(v.begin(), v.end(), min(c[i], c[j]));
                if (it != v.end() && (*it) == max(c[i], c[j])) {
                    rn.push_back({r[i], min(c[i], c[j]) + 1, max(c[i], c[j]) - 1 });
                }
            }
            if (c[i] == c[j]) {
                if (abs(r[i] - r[j]) == 1) {
                    cout << -1 << '\n';
                    return;
                }
                auto& v = hc[c[i]];
                auto it = upper_bound(v.begin(), v.end(), min(r[i], r[j]));
                if (it != v.end() && (*it) == max(r[i], r[j])) {
                    cn.push_back({c[i], min(r[i], r[j]) + 1, max(r[i], r[j]) - 1 });
                }
            }
        }
    }

    int tot = rn.size() + cn.size(); idx = 2;
    for (int i = 1; i <= tot + 2; i++)h[i] = 0, vis[i] = 0;
    s = tot + 1, t = s + 1;
    for (int i = 0; i < cn.size(); i++)add(i + 1 + rn.size(), t, 1);
    for (int i = 0; i < rn.size(); i++)
    {
        add(s, i + 1, 1);
        for (int j = 0; j < cn.size(); j++) {
            auto [x, l1, r1] = rn[i];
            auto [y, l2, r2] = cn[j];
            if (x >= l2 && x <= r2 && y >= l1 && y <= r1)add(i + 1, j + 1 + rn.size(), 1);
        }
    }
    int ans = tot;
    while (bfs())
    {
        memcpy(cur, h, sizeof h);
        ans -= dfs(s, 1e18);
    }
    cout << ans << '\n';
    for (int i = 2; i < idx; i += 2)
    {
        int u = e[i], v = e[i ^ 1];
        if (u <= tot && v <= tot)
        {
            if (w[i] == 0) {
                if (u >= rn.size())swap(u, v);
                auto [x, l1, r1] = rn[u - 1];
                auto [y, l2, r2] = cn[v - 1 - rn.size()];
                cout << x << ' ' << y << '\n';
                vis[u] = vis[v] = 1;
            }
        }
    }
    for (int i = 0; i < rn.size(); i++)
    {
        if (vis[i + 1])continue;
        auto [x, l1, r1] = rn[i];
        cout << x << ' ' << l1 << '\n';
    }
    for (int i = 0; i < cn.size(); i++)
    {
        if (vis[i + 1])continue;
        auto [y, l1, r1] = cn[i];
        cout << l1 << ' ' << y << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

详细

Test #1:

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

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
4 6
2 3
0
1
2 3
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 7684kb

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
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
13 10
30 34
0
3
20 30
43 25
31 17
0
-1
3
16 36
25 7
17 39
6
7 5
8 11
5 5
6 4
5 5
4 9

result:

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