QOJ.ac

QOJ

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

Judging History

This is the latest submission verdict.

  • [2024-10-04 20:06:56]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3760kb
  • [2024-10-04 20:06:56]
  • 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(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)