oj.uz

Submission #227054

# Submission time Handle Problem Language Result Execution time Memory
227054 2020-04-25T23:25:14 Z abeker Matching (COCI20_matching) C++17
58 / 110
 995 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 = 1.5e7 + 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;
		}
		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;
bool sol[MAXV];
char bio[MAXV];
stack <int> order;
Graph adj(MAXV), rev(MAXV);

inline int add_variables(int vars) {
	n += vars;
	assert(2 * n < MAXV);
	return n - vars;
}

void add_edge(int u, int v) {
	adj.add(u, v);
	rev.add(v, 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 dfs_forward(int x) {
	bio[x] = 1;
	for (Node* ptr = adj.head[x]; ptr != nullptr; ptr = ptr -> nxt)
		if (!bio[ptr -> val])
			dfs_forward(ptr -> val);
	order.push(x);
}

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

void dfs_backward(int x) {
	if (bio[x ^ 1] == -1)
		bye();
	bio[x] = -1;
	sol[x] = bio[x ^ 1];
	for (Node* ptr = rev.head[x]; ptr != nullptr; ptr = ptr -> nxt)
		if (!bio[ptr -> val])
			dfs_backward(ptr -> val);
	bio[x] = 1;
}

void two_sat() {
	for (int i = 0; i < 2 * n; i++)
		if (!bio[i])
			dfs_forward(i);
	for (int i = 0; i < 2 * n; i++)
		bio[i] = 0;
	for (; !order.empty(); order.pop())
		if (!bio[order.top()])
			dfs_backward(order.top());
}

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> 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] ? 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())
		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] = 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) 
			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) 
		if (off[x])
			update(x, get_bounds(x, down), get_bounds(x, up + 1), var);
}
 
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();
	
	puts("DA");
	for (auto it : segs)
		if (sol[2 * it.first])
			printf("%d %d\n", it.second.first + 1, it.second.second + 1);
}
 
int main() {
	double timer = clock();
	load();
	solve();
	fprintf(stderr, "%lf\n", (clock() - timer) / CLOCKS_PER_SEC);
	return 0;
}

Compilation message

matching.cpp: In function 'void add_clause(int, int, int)':
matching.cpp:132: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: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:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
matching.cpp:109: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 191 ms 248824 KB Output is correct
2 Correct 174 ms 248696 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 248824 KB Output is correct
2 Correct 174 ms 248696 KB Output is correct
3 Correct 175 ms 248740 KB Output is correct
4 Correct 196 ms 248696 KB Output is correct
5 Correct 203 ms 248696 KB Output is correct
6 Correct 170 ms 248696 KB Output is correct
7 Correct 201 ms 248728 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 248824 KB Output is correct
2 Correct 174 ms 248696 KB Output is correct
3 Correct 175 ms 248740 KB Output is correct
4 Correct 196 ms 248696 KB Output is correct
5 Correct 203 ms 248696 KB Output is correct
6 Correct 170 ms 248696 KB Output is correct
7 Correct 201 ms 248728 KB Output is correct
8 Correct 183 ms 248952 KB Output is correct
9 Correct 200 ms 248928 KB Output is correct
10 Correct 202 ms 248952 KB Output is correct
11 Correct 176 ms 248948 KB Output is correct
12 Correct 176 ms 248876 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 248824 KB Output is correct
2 Correct 174 ms 248696 KB Output is correct
3 Correct 175 ms 248740 KB Output is correct
4 Correct 196 ms 248696 KB Output is correct
5 Correct 203 ms 248696 KB Output is correct
6 Correct 170 ms 248696 KB Output is correct
7 Correct 201 ms 248728 KB Output is correct
8 Correct 183 ms 248952 KB Output is correct
9 Correct 200 ms 248928 KB Output is correct
10 Correct 202 ms 248952 KB Output is correct
11 Correct 176 ms 248948 KB Output is correct
12 Correct 176 ms 248876 KB Output is correct
13 Correct 181 ms 253048 KB Output is correct
14 Correct 184 ms 253052 KB Output is correct
15 Correct 185 ms 253048 KB Output is correct
16 Correct 213 ms 252924 KB Output is correct
17 Correct 185 ms 253176 KB Output is correct
18 Correct 214 ms 252920 KB Output is correct
19 Correct 207 ms 252920 KB Output is correct
20 Correct 191 ms 253048 KB Output is correct
21 Correct 216 ms 252920 KB Output is correct
22 Correct 181 ms 252920 KB Output is correct
23 Correct 182 ms 253360 KB Output is correct
24 Correct 188 ms 253304 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 248824 KB Output is correct
2 Correct 174 ms 248696 KB Output is correct
3 Correct 175 ms 248740 KB Output is correct
4 Correct 196 ms 248696 KB Output is correct
5 Correct 203 ms 248696 KB Output is correct
6 Correct 170 ms 248696 KB Output is correct
7 Correct 201 ms 248728 KB Output is correct
8 Correct 183 ms 248952 KB Output is correct
9 Correct 200 ms 248928 KB Output is correct
10 Correct 202 ms 248952 KB Output is correct
11 Correct 176 ms 248948 KB Output is correct
12 Correct 176 ms 248876 KB Output is correct
13 Correct 181 ms 253048 KB Output is correct
14 Correct 184 ms 253052 KB Output is correct
15 Correct 185 ms 253048 KB Output is correct
16 Correct 213 ms 252924 KB Output is correct
17 Correct 185 ms 253176 KB Output is correct
18 Correct 214 ms 252920 KB Output is correct
19 Correct 207 ms 252920 KB Output is correct
20 Correct 191 ms 253048 KB Output is correct
21 Correct 216 ms 252920 KB Output is correct
22 Correct 181 ms 252920 KB Output is correct
23 Correct 182 ms 253360 KB Output is correct
24 Correct 188 ms 253304 KB Output is correct
25 Correct 984 ms 379612 KB Output is correct
26 Correct 925 ms 379656 KB Output is correct
27 Correct 927 ms 379636 KB Output is correct
28 Correct 899 ms 379848 KB Output is correct
29 Correct 995 ms 379528 KB Output is correct
30 Correct 867 ms 379528 KB Output is correct
31 Correct 881 ms 379660 KB Output is correct
32 Correct 977 ms 379400 KB Output is correct
33 Correct 924 ms 366852 KB Output is correct
34 Correct 766 ms 367104 KB Output is correct
35 Correct 522 ms 355080 KB Output is correct
36 Runtime error 716 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Halted 0 ms 0 KB -