Submission #227021

#	Time	Username	Problem	Language	Result	Execution time	Memory
227021		abeker	Matching (COCI20_matching)	C++17	58 / 110	2594 ms	435948 KiB

matching

#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;

const int MAXN = 1e5 + 5;
const int offset = 1 << 17;

class TwoSat {
	int n;
	vector <int> sol;
	vector <bool> bio;
	vector <int> comp;
	vector <vector <int>> adj, rev;
	stack <int> order;
	public:
		int add_variables(int vars) {
			n += vars;
			for (int i = 0; i < 2 * vars; i++) {
				sol.push_back(0);
				bio.push_back(false);
				comp.push_back(0);
				adj.push_back(vector <int> ());
				rev.push_back(vector <int> ());
			}
			return n - vars;
		}
		TwoSat(int _n) {
			n = 0;
			add_variables(_n);
		}
		TwoSat(){}
		void add_edge(int u, int v) {
			adj[u].push_back(v);
			rev[v].push_back(u);
		}
		void add_implication(int u1, int neg1, int u2, int neg2) {
			add_edge(2 * u1 + neg1, 2 * u2 + neg2);
			add_edge(2 * u2 + !neg2, 2 * u1 + !neg1);
		}
		void set_variable(int u, bool val) {
			add_implication(u, val, u, !val);
		}
		void at_most_one(const vector <pii> &v) {
			int sz = v.size();
			add_variables(sz);
			for (int i = 0; i < sz; i++) {
				add_implication(v[i].first, v[i].second, n - i - 1, 0);
				if (i) {
					add_implication(n - i, 0, n - i - 1, 0);
					add_implication(n - i, 0, v[i].first, !v[i].second);
				}
			}
		}
		void dfs_forward(int x) {
			bio[x] = true;
			for (auto it : adj[x])
				if (!bio[it])
					dfs_forward(it);
			order.push(x);
		}
		void dfs_backward(int x, int c) {
			comp[x] = c;
			for (auto it : rev[x])
				if (!comp[it])
					dfs_backward(it, c);
		}
		bool solve() {
			for (int i = 0; i < 2 * n; i++)
				if (!bio[i])
					dfs_forward(i);
			int ptr = 0;
			for (; !order.empty(); order.pop())
				if (!comp[order.top()])
					dfs_backward(order.top(), ++ptr);
			for (int i = 0; i < 2 * n; i++) {
				if (comp[i] == comp[i ^ 1])
					return false;
				sol[i] = comp[i] > comp[i ^ 1];
			}
			return true;
		}
		int get(int u, int neg) {
			return sol[2 * u + neg];
		}
};

int N;
int x[MAXN], y[MAXN];
vector <pii> tour[2 * offset];
int st[2 * offset], off[2 * offset];
vector <int> hor[MAXN], ver[MAXN];
unordered_map <int, pii> segs;
vector <int> adj[MAXN];
TwoSat Segments;

void load() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d%d", x + i, y + i);
		hor[y[i]].push_back(i);
		ver[x[i]].push_back(i);
	}
}

void insert(int x, int lo, int hi, int from, int to, int var, int height) {
	if (lo >= to || hi <= from)	
		return;
	if (lo >= from && hi <= to) {
		tour[x].push_back({height, var});
		return;
	}
	int mid = (lo + hi) / 2;
	insert(2 * x, lo, mid, from, to, var, height);
	insert(2 * x + 1, mid, hi, from, to, var, height);
}

inline int get_id(int node, int x) {
	return x < off[node] ? st[node] + x : tour[node][x - off[node]].second;
}

void add_clause(int x, int u, int v) {
	if (u < off[x] + tour[x].size())
		Segments.add_implication(get_id(x, u), 0, get_id(x, v), 0);
}
	
void init(int x) {
	if (tour[x].empty())
		return;
	off[x] = 1;
	sort(tour[x].begin(), tour[x].end());
	while (off[x] < tour[x].size())
		off[x] *= 2;
	st[x] = Segments.add_variables(2 * off[x]);
	for (int i = 0; i < off[x]; i++) {
		add_clause(x, 2 * i, i);
		add_clause(x, 2 * i + 1, i);
	}
}

int get_bounds(int x, int val) {
	int lo = 0, hi = tour[x].size();
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (tour[x][mid].first >= val)
			hi = mid;
		else
			lo = mid + 1;
	}
	return lo;
}

void update(int node, int from, int to, int var) {
	from += off[node];
	to += off[node];
	while (from < to) {
		if (from % 2) 
			Segments.add_implication(get_id(node, from++), 0, var, 1);
		if (to % 2) 
			Segments.add_implication(get_id(node, --to), 0, var, 1);
		from /= 2;
		to /= 2;
	}
}

void add_intersections(int x, int down, int up, int var) {
	for (x += offset; x; x /= 2) 
		if (off[x])
			update(x, get_bounds(x, down), get_bounds(x, up + 1), var);
}

void bye() {
	puts("NE");
	exit(0);
}

void solve() {
	for (int i = 1; i < MAXN; i++) 
		if (hor[i].size() == 2) {
			int tmp = Segments.add_variables(1);
			segs[tmp] = {hor[i][0], hor[i][1]};
			int l = MAXN, r = 0;
			for (auto it : hor[i]) {
				adj[it].push_back(tmp);
				l = min(l, x[it]);
				r = max(r, x[it]);
			}
			insert(1, 0, offset, l, r + 1, tmp, i);
		}
	
	for (int i = 0; i < 2 * offset; i++)
		init(i);
	
	for (int i = 1; i < MAXN; i++) 
		if (ver[i].size() == 2) {
			int tmp = Segments.add_variables(1);
			segs[tmp] = {ver[i][0], ver[i][1]};
			int l = MAXN, r = 0;
			for (auto it : ver[i]) {
				adj[it].push_back(tmp);
				l = min(l, y[it]);
				r = max(r, y[it]);
			}
			add_intersections(i, l, r, tmp);
		}
	
	for (int i = 0; i < N; i++) 
		if (!adj[i].empty())
			Segments.add_implication(adj[i][0], 1, adj[i][1 % adj[i].size()], 0);
		else
			bye();
	
	if (!Segments.solve())
		bye();
	
	puts("DA");
	for (auto it : segs)
		if (Segments.get(it.first, 0))
			printf("%d %d\n", it.second.first + 1, it.second.second + 1);
}

int main() {
	load();
	solve();
	return 0;
}

Compilation message (stderr)

matching.cpp: In function 'void add_clause(int, int, int)':
matching.cpp:123:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (u < off[x] + tour[x].size())
      ~~^~~~~~~~~~~~~~~~~~~~~~~~~
matching.cpp: In function 'void init(int)':
matching.cpp:132:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (off[x] < tour[x].size())
         ~~~~~~~^~~~~~~~~~~~~~~~
matching.cpp: In function 'void load()':
matching.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
matching.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", x + i, y + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 40 / 40
• Subtask 5: 0 / 52