QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#682664 | #9412. Stop the Castle | yangyl | WA | 0ms | 3836kb | C++20 | 6.8kb | 2024-10-27 16:47:14 | 2024-10-27 16:47:16 |
Judging History
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<pair<int, int>> row, col;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (r[i] != r[j] && c[i] != c[j])
continue;
int st = (r[i] == r[j]);
for (int k = 0; k < m; k++) {
if (br[k] == r[i] && st && bc[k] > min(c[i], c[j]) && bc[k] < max(c[i], c[j])) {
st = -1;
} else if (bc[k] == c[i] && !st && br[k] > min(r[i], r[j]) && br[k] < max(r[i], r[j])) {
st = -1;
}
}
if (st == 1) {
row.emplace_back(i, j);
} else if (st == 0) {
col.emplace_back(i, j);
}
}
}
sort(row.begin(), row.end(), [&](auto x, auto y) {
return abs(c[x.first] - c[x.second]) < abs(c[y.first] - c[y.second]);
});
sort(row.begin(), row.end(), [&](auto x, auto y) {
return abs(r[x.first] - r[x.second]) < abs(r[y.first] - r[y.second]);
});
vector<pair<int, int>> rt, ct;
vector<bool> rst(row.size()), cst(col.size());
for (int i = 0; i < row.size(); i++) {
if (rst[i]) continue;
rt.push_back(row[i]);
auto [i1, i2] = row[i];
int c1 = min(c[i1], c[i2]);
int c2 = max(c[i1], c[i2]);
for (int j = i + 1; j < row.size(); j++) {
auto [j1, j2] = row[j];
if (r[i1] == r[j1] && c1 > min(c[j1], c[j2]) && c2 < max(c[j1], c[j2])) {
rst[j] = true;
}
}
}
for (int i = 0; i < col.size(); i++) {
if (cst[i]) continue;
ct.push_back(col[i]);
auto [i1, i2] = col[i];
int r1 = min(r[i1], r[i2]);
int r2 = max(r[i1], r[i2]);
for (int j = i + 1; j < col.size(); j++) {
auto [j1, j2] = col[j];
if (c[i1] == c[j1] && r1 > min(r[j1], r[j2]) && r2 < max(r[j1], r[j2])) {
cst[j] = true;
}
}
}
col = move(ct);
row = move(rt);
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: 3836kb
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: 3576kb
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 26 16 10 16 10 12 6 34 50 0 1 16 10 0 1 43 22 5 33 44 44 45 1 3 1 13 1 3 0 4 44 15 27 41 29 26 8 1 1 32 9 0 0 0 0 7 12 34 23 10 23 44 29 21 23 10 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 Duplicated position (16, 10) (test case 2)