QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#634768 | #9412. Stop the Castle | ji_114514 | WA | 1ms | 7932kb | C++20 | 4.2kb | 2024-10-12 18:02:56 | 2024-10-12 18:03:04 |
Judging History
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)