QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#611247#9412. Stop the CastleDung1604WA 1ms4088kbC++1416.7kb2024-10-04 20:04:152024-10-04 20:04:18

Judging History

This is the latest submission verdict.

  • [2024-10-04 20:04:18]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4088kb
  • [2024-10-04 20:04:15]
  • Submitted

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();
	}
	























}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3784kb

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: 3828kb

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: 4088kb

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: 3764kb

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)