QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#611262 | #9412. Stop the Castle | Dung1604 | WA | 1ms | 3760kb | C++14 | 16.7kb | 2024-10-04 20:06:56 | 2024-10-04 20:06:56 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define inf 100000007
#define mod 998244353
using namespace std;
const int BLOCK = 450;
struct edge {
int to, capacity, flow, id;
};
struct Dinic {
int Inf;
int numbVertex;
std::vector <int> pos;
std::vector <std::vector <edge> > adj;
std::vector <int> level;
int source, sink;
Dinic(int _numbVertex, int _source, int _sink, int _inf) {
numbVertex = _numbVertex;
source = _source;
sink = _sink;
adj.clear();
adj.resize(numbVertex);
level.clear();
level.resize(numbVertex);
pos.clear();
pos.resize(numbVertex, 0);
Inf = _inf;
}
void addEdge(int u, int v, int weight) {
int szu = (int)adj[u].size();
int szv = (int)adj[v].size();
adj[u].push_back({ v, weight, 0, szv });
adj[v].push_back({ u, 0, 0, szu });
}
bool bfs() {
for (int i = 0; i < numbVertex; i++) {
level[i] = -1;
}
std::queue <int> myqueue;
myqueue.push(source);
level[source] = 0;
while (myqueue.empty() == false) {
int u = myqueue.front();
myqueue.pop();
for (int i = 0; i < (int)adj[u].size(); i++) {
edge neighbor = adj[u][i];
if (neighbor.flow < neighbor.capacity && level[neighbor.to] == -1) {
level[neighbor.to] = level[u] + 1;
myqueue.push(neighbor.to);
}
}
}
return (level[sink] != -1);
}
int sendFlow(int u, int sink, int currentFlow) {
if (u == sink) {
return currentFlow;
}
for (; pos[u] < (int)adj[u].size(); pos[u]++) {
edge& neighbor = adj[u][pos[u]];
if (level[neighbor.to] == level[u] + 1 && neighbor.flow < neighbor.capacity) {
int flow = sendFlow(neighbor.to, sink, std::min(currentFlow, neighbor.capacity - neighbor.flow));
if (flow > 0) {
neighbor.flow += flow;
edge& rev = adj[neighbor.to][neighbor.id];
rev.flow -= flow;
return flow;
}
}
}
return 0;
}
int dinicMaxFlow() {
int ret = 0LL;
while (bfs() == true) {
for (int i = 0; i < numbVertex; i++) {
pos[i] = 0;
}
while (true) {
int flow = sendFlow(source, sink, inf);
if (flow == 0) {
break;
}
ret += flow;
}
}
return ret;
}
};
int source, sink;
ll fastpow(ll n, ll x) {
if (x == 0) {
return 1;
}
else {
ll ret = fastpow(n, x / 2);
ret = ((ret) % mod * (ret) % mod) % mod;
if (x % 2 == 0) {
return ret;
}
else {
return ((ret % mod) * (n % mod)) % mod;
}
}
}
ll gcd(ll a, ll b) {
if (b == 0) {
return a;
}
else {
return gcd(b, a % b);
}
}
ll lcm(ll a, ll b) {
ll val = (a % mod * b % mod) % mod;
val = (val * fastpow(gcd(a, b), mod - 2)) % mod;
return val;
}
ll Logk(ll n, ll k) {
if (k == 1) {
return 1;
}
if (n == 0) {
return 0;
}
int count = -1;
while (n > 0) {
count++;
n /= k;
}
return count;
}
struct Dsu {
vector<int> par;
void init(int n) {
par.resize(n + 5, 0);
for (int i = 1; i <= n; i++) par[i] = i;
}
int find(int u) {
if (par[u] == u) return u;
return par[u] = find(par[u]);
}
bool join(int u, int v) {
u = find(u); v = find(v);
if (u == v) return false;
par[v] = u;
return true;
}
} dsu;
class Solution {
public:
int cost[201][201]; //cost matrix
int n, max_match; //n workers and n jobs
int lx[201], ly[201]; //labels of X and Y parts
int xy[201]; //xy[x] - vertex that is matched with x,
int yx[201]; //yx[y] - vertex that is matched with y
bool S[201], T[201]; //sets S and T in algorithm
int slack[201]; //as in the algorithm description
int slackx[201]; //slackx[y] such a vertex, that
int prev_ious[201]; //array for memorizing alternating p
void init_labels()
{
memset(lx, 0, sizeof(lx));
memset(ly, 0, sizeof(ly));
for (int x = 0; x < n; x++)
for (int y = 0; y < n; y++)
lx[x] = max(lx[x], cost[x][y]);
}
void update_labels()
{
int x, y;
int delta = 99999999; //init delta as infinity
for (y = 0; y < n; y++) //calculate delta using slack
if (!T[y])
delta = min(delta, slack[y]);
for (x = 0; x < n; x++) //update X labels
if (S[x])
lx[x] -= delta;
for (y = 0; y < n; y++) //update Y labels
if (T[y])
ly[y] += delta;
for (y = 0; y < n; y++) //update slack array
if (!T[y])
slack[y] -= delta;
}
void add_to_tree(int x, int prev_iousx)
//x - current vertex,prev_iousx - vertex from X before x in the alternating path,
//so we add edges (prev_iousx, xy[x]), (xy[x], x)
{
S[x] = true; //add x to S
prev_ious[x] = prev_iousx; //we need this when augmenting
for (int y = 0; y < n; y++) //update slacks, because we add new vertex to S
if (lx[x] + ly[y] - cost[x][y] < slack[y])
{
slack[y] = lx[x] + ly[y] - cost[x][y];
slackx[y] = x;
}
}
void augment() //main function of the algorithm
{
if (max_match == n) return; //check whether matching is already perfect
int x, y, root; //just counters and root vertex
int q[201], wr = 0, rd = 0; //q - queue for bfs, wr,rd - write and read
//pos in queue
memset(S, false, sizeof(S)); //init set S
memset(T, false, sizeof(T)); //init set T
memset(prev_ious, -1, sizeof(prev_ious)); //init set prev_ious - for the alternating tree
for (x = 0; x < n; x++) //finding root of the tree
{
if (xy[x] == -1)
{
q[wr++] = root = x;
prev_ious[x] = -2;
S[x] = true;
break;
}
}
for (y = 0; y < n; y++) //initializing slack array
{
slack[y] = lx[root] + ly[y] - cost[root][y];
slackx[y] = root;
}
//second part of augment() function
while (true) //main cycle
{
while (rd < wr) //building tree with bfs cycle
{
x = q[rd++]; //current vertex from X part
for (y = 0; y < n; y++) //iterate through all edges in equality graph
if (cost[x][y] == lx[x] + ly[y] && !T[y])
{
if (yx[y] == -1) break; //an exposed vertex in Y found, so
//augmenting path exists!
T[y] = true; //else just add y to T,
q[wr++] = yx[y]; //add vertex yx[y], which is matched
//with y, to the queue
add_to_tree(yx[y], x); //add edges (x,y) and (y,yx[y]) to the tree
}
if (y < n)
break; //augmenting path found!
}
if (y < n)
break; //augmenting path found!
update_labels(); //augmenting path not found, so improve labeling
wr = rd = 0;
for (y = 0; y < n; y++)
//in this cycle we add edges that were added to the equality graph as a
//result of improving the labeling, we add edge (slackx[y], y) to the tree if
//and only if !T[y] && slack[y] == 0, also with this edge we add another one
//(y, yx[y]) or augment the matching, if y was exposed
if (!T[y] && slack[y] == 0)
{
if (yx[y] == -1) //exposed vertex in Y found - augmenting path exists!
{
x = slackx[y];
break;
}
else
{
T[y] = true; //else just add y to T,
if (!S[yx[y]])
{
q[wr++] = yx[y]; //add vertex yx[y], which is matched with
//y, to the queue
add_to_tree(yx[y], slackx[y]); //and add edges (x,y) and (y,
//yx[y]) to the tree
}
}
}
if (y < n) break; //augmenting path found!
}
if (y < n) //we found augmenting path!
{
max_match++; //increment matching
//in this cycle we inverse edges along augmenting path
for (int cx = x, cy = y, ty; cx != -2; cx = prev_ious[cx], cy = ty)
{
ty = xy[cx];
yx[cy] = cx;
xy[cx] = cy;
}
augment(); //recall function, go to step 1 of the algorithm
}
}//end of augment() function
vector<pair<int, int>> hungarian()
{
int ret = 0; //weight of the optimal matching
max_match = 0; //number of vertices in current matching
memset(xy, -1, sizeof(xy));
memset(yx, -1, sizeof(yx));
init_labels(); //step 0
augment(); //steps 1-3
vector<pair<int, int>> ans;
for (int x = 0; x < n; x++) { //forming answer there
ret += cost[x][xy[x]];
ans.push_back({ x, xy[x] });
}
return ans;
}
vector<pair<int, int>> assignmentProblem(ll Arr[], int N) {
n = N;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cost[i][j] = -1 * Arr[i * n + j];
return hungarian();
}
};
vector<pair<ll, ll>> node;
pair<ll, ll> point[205];
pair<ll, ll> obs[205];
vector<pair < ll, ll >> ans;
set<pair<ll, ll>> good;
map<pair<ll, ll>, set<pair<ll, ll>>> block;
map<ll, vector<pair<ll, ll>>> hang;
map<ll, vector<pair<ll, ll>>> cot;
vector<vector<pair<bool, ll>>> a(205);
set<pair<ll, ll>> ngang;
set<pair<ll, ll>> doc;
map<pair<ll, ll>, ll> convertX;
map<ll, pair<ll, ll>> convertXBack;
map<pair<ll, ll>, ll> convertY;
map<ll, pair<ll, ll>> convertYBack;
map<pair<ll, ll>, ll> convertBack;
ll f[200005];
void solve() {
ll n;
cin >> n;
ngang.clear();
doc.clear();
convertX.clear();
convertY.clear();
convertBack.clear();
convertXBack.clear();
convertYBack.clear();
ans.clear();
node.clear();
good.clear();
block.clear();
hang.clear();
cot.clear();
for (int i = 1; i <= n; i++) {
cin >> point[i].first >> point[i].second;
hang[point[i].first].push_back({ point[i].second, i });
cot[point[i].second].push_back({ point[i].first,i });
a[i].clear();
}
ll m;
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> obs[i].first >> obs[i].second;
}
for (int i = 1; i <= n; i++) {
ll x = point[i].first;
ll y = point[i].second;
ll right = inf;
ll posRight = -1;
ll left = 0;
ll posLeft = -1;
ll up = 0;
ll down = inf;
ll posUp = -1;
ll posDown = -1;
for (int j = 0; j < hang[x].size(); j++) {
ll y2 = hang[x][j].first;
if (y2 > y && y2 < right) {
right = min(right, y2);
posRight = hang[x][j].second;
}
else if (y2 < y && y2 > right) {
left = max(left, y2);
posLeft = hang[x][j].second;
}
}
if (posRight != -1) {
a[i].push_back({ false, posRight });
}
if (posLeft != -1) {
a[i].push_back({ false, posLeft });
}
for (int j = 0; j < cot[y].size(); j++) {
ll x2 = cot[y][j].first;
if (x2 > x && x2 < down) {
down = min(down, x2);
posDown = cot[y][j].second;
}
else if (x2 < x && x2 > up) {
up = max(up, x2);
posUp = cot[y][j].second;
}
}
if (posUp != -1) {
a[i].push_back({ false, posUp });
}
if (posDown != -1) {
a[i].push_back({ false, posDown });
}
}
for (int i = 1; i <= n; i++) {
ll x = point[i].first;
ll y = point[i].second;
for (int j = 0; j < a[i].size(); j++) {
ll x2 = point[a[i][j].second].first;
ll y2 = point[a[i][j].second].second;
ll u = a[i][j].second;
if (x2 == x) {
if (abs(y2 - y) == 1) {
cout << -1 << endl;
return;
}
else {
bool blocked = false;
for (int z = 1; z <= m; z++) {
ll x3 = obs[z].first;
ll y3 = obs[z].second;
if (x3 == x2 && y3 > min(y2, y) && y3 < max(y2, y)) {
blocked = true;
}
}
a[i][j].first = blocked;
}
}
if (y2 == y) {
if (abs(x2 - x) == 1) {
cout << -1 << endl;
return;
}
else {
bool blocked = false;
for (int z = 1; z <= m; z++) {
ll x3 = obs[z].first;
ll y3 = obs[z].second;
if (y3 == y2 && x3 > min(x2, x) && x3 < max(x2, x)) {
blocked = true;
}
}
a[i][j].first = blocked;
}
}
}
}
for (ll i = 1; i <= n; i++) {
ll x = point[i].first;
ll y = point[i].second;
for (ll j = 0; j < a[i].size(); j++) {
ll x2 = point[a[i][j].second].first;
ll y2 = point[a[i][j].second].second;
ll u = a[i][j].second;
if (x2 == x) {
if (abs(y2 - y) == 1) {
cout << -1 << endl;
return;
}
else {
if (!a[i][j].first) {
bool have = false;
for (int z = 1; z <= n; z++) {
ll x4 = point[z].first;
ll y4 = point[z].second;
if (z != i && z != u) {
for (int t = 0; t < a[z].size(); t++) {
ll x3 = point[a[z][t].second].first;
ll y3 = point[a[z][t].second].second;
int v = a[z][t].second;
if (v != i && v != u) {
if (y4 == y3 && !a[z][t].first) {
if (max(x4, x3) > x && min(x4, x3) < x && y3 > min(y, y2) && y3 < max(y, y2)) {
block[{x, y3}].insert({ min(i, u), max(i, u) });
block[{x, y3}].insert({ min(z, v), max(z, v) });
good.insert({ x, y3 });
have = true;
}
}
}
}
}
}
if (!have) {
block[{ x, min(y, y2) + 1 }].insert({ min(i, u), max(i, u) });
good.insert({ x, min(y, y2) + 1 });
}
}
}
}
if (y2 == y) {
if (abs(x2 - x) == 1) {
cout << -1 << endl;
return;
}
else {
if (!a[i][j].first) {
bool have = false;
for (int z = 1; z <= n; z++) {
ll x4 = point[z].first;
ll y4 = point[z].second;
if (z != i && z != u) {
for (int t = 0; t < a[z].size(); t++) {
ll x3 = point[a[z][t].second].first;
ll y3 = point[a[z][t].second].second;
int v = a[z][t].second;
if (v!= u && v!= i && x4 == x3 && !a[z][t].first) {
if (max(y4, y3) > y && min(y4, y3) < y && x3 > min(x, x2) && x3 < max(x, x2)) {
block[{x3, y}].insert({ min(i, u), max(i, u) });
block[{x3, y}].insert({ min(z, v), max(z, v) });
good.insert({ x3, y });
have = true;
}
}
}
}
}
if (!have) {
block[{ min(x, x2) + 1, y }].insert({ min(i, u), max(i, u) });
good.insert({ min(x, x2) + 1, y });
}
}
}
}
}
}
for (auto it = good.begin(); it != good.end(); it++) {
if (block[{it->first, it->second}].size() == 1) {
ans.push_back({ it->first, it->second });
}
else {
auto it2 = block[{it->first, it->second}].begin();
int u = it2->first;
int v = it2->second;
if (point[u].first == point[v].first) {
ngang.insert({ u, v });
it2++;
doc.insert(*it2);
}
else {
doc.insert({ u, v });
it2++;
ngang.insert(*it2);
}
node.push_back({ it->first, it->second });
}
}
int size = max(ngang.size(), doc.size());
int cur = 0;
for (auto it = ngang.begin(); it != ngang.end(); it++) {
convertX[*it] = cur;
convertXBack[cur] = *it;
cur++;
}
cur = 0;
for (auto it = doc.begin(); it != doc.end(); it++) {
convertY[*it] = cur;
convertYBack[cur] = *it;
cur++;
}
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
f[i * size + j] = 99999;
}
}
for (int i = 0; i < node.size(); i++) {
auto it = block[node[i]].begin();
int u = it->first;
int v = it->second;
int x = -1;
int y = -1;
if (point[u].first == point[v].first) {
x = convertX[*it];
it++;
y = convertY[*it];
}
else {
y = convertY[*it];
it++;
x = convertX[*it];
}
f[x*size + y] = 1;
convertBack[{x, y}] = i;
}
Solution ob;
if (1) {
vector<pair<int, int>> option = ob.assignmentProblem(f, size);
for (int i = 0; i < option.size(); i++) {
if (f[option[i].first * size + option[i].second] == 1) {
ans.push_back(node[convertBack[{option[i].first, option[i].second}]]);
ngang.erase(convertXBack[option[i].first]);
doc.erase(convertYBack[option[i].second]);
}
}
for (int i = 0; i < node.size(); i++) {
auto it = block[node[i]].begin();
ll u = it->first;
ll v = it->second;
if (point[u].first == point[v].first) {
auto it2 = ngang.find(*it);
if (it2 != ngang.end()) {
ngang.erase(it2);
it++;
it2 = doc.find(*it);
if (it2 != doc.end()) {
doc.erase(it2);
}
ans.push_back({ node[i].first , node[i].second });
}
else {
it++;
it2 = doc.find(*it);
if (it2 != doc.end()) {
doc.erase(it2);
ans.push_back({ node[i].first , node[i].second });
}
}
}
else {
auto it2 = doc.find(*it);
if (it2 !=doc.end()) {
doc.erase(it2);
it++;
it2 = ngang.find(*it);
if (it2 != ngang.end()) {
ngang.erase(it2);
}
ans.push_back({ node[i].first , node[i].second });
}
else {
it++;
it2 = ngang.find(*it);
if (it2 != ngang.end()) {
ngang.erase(it2);
ans.push_back({ node[i].first , node[i].second });
}
}
}
}
}
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i--) {
cout << ans[i].first << " " << ans[i].second << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while (t--) {
solve();
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3760kb
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 0 1 2 3 -1
result:
wrong answer Integer parameter [name=x_i] equals to 0, violates the range [1, 10^9] (test case 1)