QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#624847 | #9412. Stop the Castle | gaofeng | WA | 0ms | 3892kb | C++23 | 5.1kb | 2024-10-09 16:43:28 | 2024-10-09 16:43:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef pair<PII,PII>PIII;
const int N=2e3+10, M = 2e3 + 10;
const int mod=998244353;
const int INF = 0x3f3f3f3f;
const ll INFll = 0x3f3f3f3f3f3f3f3f;
#define endl "\n"
#define x first
#define y second
PIII L[N], R[N];
int lcnt, rcnt;
int S, T;
int h[N], ne[M], e[M], f[M], idx;
int d[N],cur[N];
bool st[N];
PII res[N];
void clear() {
// cout << S << " " << T << endl;
for(int i = S; i < T; i ++) {
h[i] = -1;
ne[i] = e[i] = f[i] = d[i] = cur[i] = 0;
st[i] = false;
R[i] = L[i] = {{0,0},{0,0}};
res[i] = {0,0};
}
S = 0, T = 0;
lcnt = rcnt = idx = 0;
}
void print(PIII t) {
cout << t.x.x << " " << t.x.y << " | " << t.y.x << " " << t.y.y << endl;
}
PII pd2(PIII a, PIII b) {
int resx = 0, resy = 0;
if(b.first.x < a.first.x && a.first.x < b.second.x) resx = a.first.x;
if(a.first.y < b.first.y && b.first.y < a.second.y) resy = b.first.y;
return {resx, resy};
}
void add(int a, int b, int c) {
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}
bool bfs() {
// memset(d, -1, sizeof(int) * (T + 10));
memset(d, -1, sizeof d);
queue<int> q;
q.push(S), d[S] = 0, cur[S] = h[S];
while(q.size()) {
int u = q.front(); q.pop();
for(int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if(d[v] == -1 && f[i]) {
d[v] = d[u] + 1;
cur[v] = h[v];
if(v == T) return true;
q.push(v);
}
}
}
return false;
}
int find(int u, int limit) {
if(u == T) return limit;
int flow = 0;
for(int i = cur[u]; ~i && flow < limit; i = ne[i]) {
int v = e[i];
cur[u] = i;
if(d[v] == d[u] + 1 && f[i]) {
int t = find(v, min(f[i], limit - flow));
if(!t) cur[u] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
ll dinic() {
ll ans = 0, flow;
while(bfs())
if(flow = find(S, INF))
ans += flow;
return ans;
}
void solve()
{
unordered_map<int,vector<PII>> row, col;
row.clear();
col.clear();
int n; cin >> n;
for(int i = 1; i <= n; i ++) {
int x, y; cin >> x >> y;
row[x].push_back({y,1});
col[y].push_back({x,1});
}
int m; cin >> m;
for(int i = 1; i <= m; i ++) {
int x, y; cin >> x >> y;
row[x].push_back({y,0});
col[y].push_back({x,0});
}
bool ky = true;
for(auto &[i,t] : row) {
sort(t.begin(), t.end());
for(int j = 1; j < t.size(); j ++) {
if(t[j].second == 0 || t[j - 1].second == 0) continue;
if(t[j].first == t[j - 1].first + 1) ky = false;
L[++lcnt] = {{i, t[j - 1].first}, {i, t[j].first}};
}
}
for(auto &[i,t] : col) {
sort(t.begin(), t.end());
for(int j = 1; j < t.size(); j ++) {
if(t[j].second == 0 || t[j - 1].second == 0) continue;
if(t[j].first == t[j - 1].first + 1) ky = false;
R[++rcnt] = {{t[j - 1].first, i}, {t[j].first, i}};
}
}
if(!ky) {
cout << "-1";
return;
}
S = 0, T = lcnt + rcnt + 1;;
for(int i = 1; i <= lcnt; i ++) {
// print(L[i]);
add(S, i, 1);
}
for(int i = 1; i <= rcnt; i ++) {
// print(R[i]);
add(i + lcnt, T, 1);
}
for(int i = 1; i <= lcnt; i ++) {
for(int j = 1; j <= rcnt; j ++) {
PII T = pd2(L[i], R[j]);
if(T.x == 0 || T.y == 0) continue;
res[idx] = T;
add(i, j + lcnt, 1);
}
}
dinic();
vector<PII> ans;
// cout << lcnt << " " << T << endl;
for(int i = 0; i < idx; i += 2) {
int v = e[i], u = e[i ^ 1];
if(0 < u && u <= lcnt && lcnt < v && v < T && f[i ^ 1]) {
// cout << u << " " << v << " " << f[i ^ 1] << " " << endl;
// cout << res[i].x << " " << res[i].y << endl;
ans.push_back(res[i]);
st[u] = st[v] = true;
}
}
for(int i = 1; i <= lcnt; i ++) {
if(!st[i]) {
ans.push_back({L[i].x.x, L[i].x.y + 1});
// cout << L[i].x.x << " " << L[i].x.y + 1 << endl;
}
}
for(int i = 1; i <= rcnt; i ++) {
if(!st[i + lcnt]) {
ans.push_back({R[i].x.x + 1, R[i].x.y});
// cout << R[i].x.x + 1 << " " << R[i].x.y << endl;
}
}
cout << ans.size() << endl;
for(auto [x, y] : ans) cout << x << " " << y << endl;
}
signed main()
{
memset(h, -1, sizeof h);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cout << setprecision(11) << fixed;
int t;t=1;
cin>>t;
for(int i=1;i<=t;i++){
//printf("Case %d: ",i);
clear();
solve();
clear();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
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: 3668kb
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 29 38 20 12 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 29 26 27 41 44 4 8 1 21 15 1 32 9 0 0 0 0 6 23 10 35 34 23 44 12 11 29 21 24 46 0 3 20 30 43 25 31 17 0 -13 16 36 25 7 17 39 6 8 9 5 5 7 3 6 4 2 11 3 10
result:
wrong answer Integer parameter [name=K] equals to -13, violates the range [-1, 256] (test case 19)