Submission #227166

#	Time	Username	Problem	Language	Result	Execution time	Memory
227166		abeker	Matching (COCI20_matching)	C++17	58 / 110	850 ms	524292 KiB

matching

#include <bits/stdc++.h>
using namespace std;
 
typedef pair <int, int> pii;
 
const int MAXN = 1e5 + 5;
const int offset = 1 << 17;
const int MAXV = 2e7 + 5;
 
struct Node {
	int val;
	Node* nxt;
};
 
class Graph {
	Node* get_node(int dest, Node* head) {
		Node* newNode = new Node;
		newNode -> val = dest;
		newNode -> nxt = head;
		return newNode;
	}
	int N;
	public:
		Node **head;
		Graph(int N) {
			head = new Node*[N]();
			this -> N = N;
			for (int i = 0; i < N; i++)
				head[i] = nullptr;
		}
		Graph(){}
		void add(int src, int dest) {
			head[src] = get_node(dest, head[src]);
		}
		~Graph() {
			for (int i = 0; i < N; i++)
				delete[] head[i];
			delete[] head;
		}
};
 
int n;
stack <int> order;
pii edges[MAXV];
int e;

inline int add_variables(int vars) {
	n += vars;
	return n - vars;
}
 
void add_edge(int u, int v) {
	edges[e++] = {u, v};
}
 
void add_implication(int u1, int neg1, int u2, int neg2) {
	if (u1 == -1 || u2 == -1)
		return;
	add_edge(2 * u1 + neg1, 2 * u2 + neg2);
	add_edge(2 * u2 + !neg2, 2 * u1 + !neg1);
}
 
void dfs_forward(int x, Graph &g, char *vis) {
	vis[x] = 1;
	for (Node* ptr = g.head[x]; ptr != nullptr; ptr = ptr -> nxt)
		if (!vis[ptr -> val])
			dfs_forward(ptr -> val, g, vis);
	order.push(x);
}
 
void bye() {
	puts("NE");
	exit(0);
}
 
void dfs_backward(int x, Graph &g, char *vis, bool *ans) {
	if (vis[x ^ 1] == -1)
		bye();
	vis[x] = -1;
	ans[x] = vis[x ^ 1];
	for (Node* ptr = g.head[x]; ptr != nullptr; ptr = ptr -> nxt)
		if (!vis[ptr -> val])
			dfs_backward(ptr -> val, g, vis, ans);
	vis[x] = 1;
}
 
int N;
int x[MAXN], y[MAXN];
int off[2 * offset];
vector <int> pos[2 * offset];
vector <pii> tour[2 * offset];
vector <int> hor[MAXN], ver[MAXN];
unordered_map <int, pii> segs;
vector <int> graph[MAXN];
 
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] && x < off[node] + tour[node].size() ? tour[node][x - off[node]].second : pos[node][x]; 
}

void add_clause(int x, int u, int v) {
	add_implication(get_id(x, u), 0, get_id(x, v), 0);	
}

bool dfs(int node, int x, vector <int> &v) {
	if (x >= off[node]) 
		return x < off[node] + tour[node].size();
	dfs(node, 2 * x, v);
	if (dfs(node, 2 * x + 1, v)) {
		v.push_back(x);
		return true;
	}
	return false;
}
	
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;
	vector <int> toAdd;
	dfs(x, 1, toAdd);
	int sz = toAdd.size();
	int st = add_variables(sz);
	pos[x].resize(2 * off[x], -1);
	for (int i = 0; i < sz; i++)
		pos[x][toAdd[i]] = st + i;
	for (auto it : toAdd) {
		add_clause(x, 2 * it, it);
		add_clause(x, 2 * it + 1, it);
	}
}
 
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) {
	if (!off[node])
		return;
	from += off[node];
	to += off[node];
	while (from < to) {
		if (from % 2) 
			add_implication(get_id(node, from++), 0, var, 1);
		if (to % 2) 
			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) 
		update(x, get_bounds(x, down), get_bounds(x, up + 1), var);
}
 
void two_sat() {
	bool *sol = new bool[2 * n];
	char *bio = new char[2 * n];
	Graph adj(2 * n), rev(2 * n);
	for (int i = 0; i < e; i++) {
		adj.add(edges[i].first, edges[i].second);
		rev.add(edges[i].second, edges[i].first);
	}
	for (int i = 0; i < 2 * n; i++)
		if (!bio[i])
			dfs_forward(i, adj, bio);
	for (int i = 0; i < 2 * n; i++)
		bio[i] = 0;
	for (; !order.empty(); order.pop())
		if (!bio[order.top()])
			dfs_backward(order.top(), rev, bio, sol);
	puts("DA");
	for (auto it : segs)
		if (sol[2 * it.first])
			printf("%d %d\n", it.second.first + 1, it.second.second + 1);
	delete[] sol;
	delete[] bio;
}
 
void solve() {
	for (int i = 1; i < MAXN; i++) 
		if (hor[i].size() == 2) {
			int tmp = add_variables(1);
			segs[tmp] = {hor[i][0], hor[i][1]};
			int l = MAXN, r = 0;
			for (auto it : hor[i]) {
				graph[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 = add_variables(1);
			segs[tmp] = {ver[i][0], ver[i][1]};
			int l = MAXN, r = 0;
			for (auto it : ver[i]) {
				graph[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 (!graph[i].empty())
			add_implication(graph[i][0], 1, graph[i][1 % graph[i].size()], 0);
		else
			bye();
	
	two_sat();
}
 
int main() {
	double timer = clock();
	load();
	solve();
	fprintf(stderr, "%lf\n", (clock() - timer) / CLOCKS_PER_SEC);
	return 0;
}

Compilation message (stderr)

matching.cpp: In function 'int get_id(int, int)':
matching.cpp:118:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return x >= off[node] && x < off[node] + tour[node].size() ? tour[node][x - off[node]].second : pos[node][x]; 
                           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
matching.cpp: In function 'bool dfs(int, int, std::vector<int>&)':
matching.cpp:127:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   return x < off[node] + tour[node].size();
          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
matching.cpp: In function 'void init(int)':
matching.cpp:141: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:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
matching.cpp:99: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