oj.uz

Submission #227166

# Submission time Handle Problem Language Result Execution time Memory
227166 2020-04-26T09:41:37 Z abeker Matching (COCI20_matching) C++17
58 / 110
 850 ms 524292 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19840 KB Output is correct
2 Correct 16 ms 19840 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19840 KB Output is correct
2 Correct 16 ms 19840 KB Output is correct
3 Correct 16 ms 19840 KB Output is correct
4 Correct 16 ms 19840 KB Output is correct
5 Correct 17 ms 19840 KB Output is correct
6 Correct 16 ms 19840 KB Output is correct
7 Correct 18 ms 19840 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19840 KB Output is correct
2 Correct 16 ms 19840 KB Output is correct
3 Correct 16 ms 19840 KB Output is correct
4 Correct 16 ms 19840 KB Output is correct
5 Correct 17 ms 19840 KB Output is correct
6 Correct 16 ms 19840 KB Output is correct
7 Correct 18 ms 19840 KB Output is correct
8 Correct 16 ms 19968 KB Output is correct
9 Correct 16 ms 19968 KB Output is correct
10 Correct 17 ms 19968 KB Output is correct
11 Correct 20 ms 20008 KB Output is correct
12 Correct 16 ms 19968 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19840 KB Output is correct
2 Correct 16 ms 19840 KB Output is correct
3 Correct 16 ms 19840 KB Output is correct
4 Correct 16 ms 19840 KB Output is correct
5 Correct 17 ms 19840 KB Output is correct
6 Correct 16 ms 19840 KB Output is correct
7 Correct 18 ms 19840 KB Output is correct
8 Correct 16 ms 19968 KB Output is correct
9 Correct 16 ms 19968 KB Output is correct
10 Correct 17 ms 19968 KB Output is correct
11 Correct 20 ms 20008 KB Output is correct
12 Correct 16 ms 19968 KB Output is correct
13 Correct 24 ms 22784 KB Output is correct
14 Correct 27 ms 22784 KB Output is correct
15 Correct 28 ms 22784 KB Output is correct
16 Correct 24 ms 22736 KB Output is correct
17 Correct 24 ms 22784 KB Output is correct
18 Correct 27 ms 22784 KB Output is correct
19 Correct 28 ms 22784 KB Output is correct
20 Correct 23 ms 22656 KB Output is correct
21 Correct 22 ms 22784 KB Output is correct
22 Correct 22 ms 22784 KB Output is correct
23 Correct 26 ms 23680 KB Output is correct
24 Correct 24 ms 23808 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19840 KB Output is correct
2 Correct 16 ms 19840 KB Output is correct
3 Correct 16 ms 19840 KB Output is correct
4 Correct 16 ms 19840 KB Output is correct
5 Correct 17 ms 19840 KB Output is correct
6 Correct 16 ms 19840 KB Output is correct
7 Correct 18 ms 19840 KB Output is correct
8 Correct 16 ms 19968 KB Output is correct
9 Correct 16 ms 19968 KB Output is correct
10 Correct 17 ms 19968 KB Output is correct
11 Correct 20 ms 20008 KB Output is correct
12 Correct 16 ms 19968 KB Output is correct
13 Correct 24 ms 22784 KB Output is correct
14 Correct 27 ms 22784 KB Output is correct
15 Correct 28 ms 22784 KB Output is correct
16 Correct 24 ms 22736 KB Output is correct
17 Correct 24 ms 22784 KB Output is correct
18 Correct 27 ms 22784 KB Output is correct
19 Correct 28 ms 22784 KB Output is correct
20 Correct 23 ms 22656 KB Output is correct
21 Correct 22 ms 22784 KB Output is correct
22 Correct 22 ms 22784 KB Output is correct
23 Correct 26 ms 23680 KB Output is correct
24 Correct 24 ms 23808 KB Output is correct
25 Correct 660 ms 135428 KB Output is correct
26 Correct 655 ms 135428 KB Output is correct
27 Correct 642 ms 135560 KB Output is correct
28 Correct 637 ms 135816 KB Output is correct
29 Correct 487 ms 135048 KB Output is correct
30 Correct 501 ms 134920 KB Output is correct
31 Correct 454 ms 135172 KB Output is correct
32 Correct 454 ms 134792 KB Output is correct
33 Correct 421 ms 123144 KB Output is correct
34 Correct 381 ms 123272 KB Output is correct
35 Correct 193 ms 46220 KB Output is correct
36 Runtime error 850 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Halted 0 ms 0 KB -