QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#611231 | #9412. Stop the Castle | Dung1604 | WA | 1ms | 3992kb | C++14 | 16.7kb | 2024-10-04 20:00:00 | 2024-10-04 20:00:00 |
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(int 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;
int f[200005];
void solve() {
int 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();
}
int 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;
int 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 (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;
int 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();
int u = it->first;
int 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 = ans.size() - 1; i >= 0; 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();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3992kb
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: 0
Accepted
time: 1ms
memory: 3832kb
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 34 18 29 38 20 12 5 34 50 20 26 16 15 16 10 12 6 0 1 16 10 0 1 43 22 5 44 45 42 44 33 10 1 13 1 3 0 5 44 4 29 26 27 41 21 15 8 1 1 32 9 0 0 0 0 6 35 34 23 10 29 21 24 46 23 44 12 11 0 3 43 25 31 17 20 30 0 -1 3 16 36 25 7 17 39 6 8 10 8 9 7 5 6 5 8 11 5 5
result:
ok ok 21 cases (21 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
2 200 7 52 9 160 10 4 12 61 18 436 19 430 20 499 24 139 25 416 29 53 33 153 35 275 35 310 37 25 38 477 39 349 42 120 44 158 45 330 49 486 50 204 51 67 52 138 52 305 56 139 63 132 66 4 67 327 70 484 71 67 72 308 74 218 76 479 81 139 82 90 86 201 87 335 91 35 91 220 92 496 94 29 94 436 96 359 97 299 1...
output:
46 311 367 260 275 393 307 352 61 349 112 334 186 311 177 306 374 277 356 270 305 224 147 199 432 187 467 185 67 154 496 154 160 132 138 126 275 126 153 94 35 91 61 52 139 453 251 440 179 415 305 390 308 380 385 311 455 286 367 278 272 277 189 274 67 271 186 261 468 240 35 224 393 187 433 138 429 57...
result:
ok ok 2 cases (2 test cases)
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3812kb
input:
20 13 89287395 441913071 89287395 590314987 142917372 582720391 142917372 598813561 232930851 582720391 263974835 468188689 263974835 490702144 543529670 152471388 543529670 219371706 647691663 598813561 772865038 598813561 773363571 482933265 773363571 561453301 8 128947560 120560639 264980960 4742...
output:
8 773363571 482933266 647691664 598813561 543529670 152471389 263974835 468188690 142917373 598813561 142917373 582720391 142917372 582720392 89287395 441913072 7 808969359 818037531 808969360 354711322 808969359 891229782 808969359 386523246 469117951 762966373 92745430 358274214 59832704 871951216...
result:
wrong answer There are still 5 pairs of castles which can attack each other (test case 4)