oj.uz

Submission #197712

# Submission time Handle Problem Language Result Execution time Memory
197712 2020-01-22T13:24:05 Z dolphingarlic ČVENK (COI15_cvenk) C++14
17 / 100
 2410 ms 93160 KB 
#include <bits/stdc++.h>
using namespace std;

long long tot_dist = 0, ans = LLONG_MAX;

struct Node {
	int x, y, l;
	Node *c[2];

	Node(int X = 0, int Y = 0): l(0), x(X), y(Y) {
		c[0] = c[1] = NULL;
	}

	Node* insert(Node *ins, int child) {
		l++;
		if (c[child] == NULL) {
			tot_dist += ins->x - x + ins->y - y;
			c[child] = ins;
			return ins;
		}
		if (ins->x < c[child]->x || ins->y < c[child]->y) {
			tot_dist += ins->x - x + ins->y - y;
			ins->c[child] = c[child];
			ins->l += c[child]->l;
			c[child] = ins;
			return ins;
		}
		if (ins->x > c[child]->x || ins->y > c[child]->y) {
			tot_dist += ins->x - c[child]->x + ins->y - c[child]->y;
			return c[child]->insert(ins, child);
		}
		tot_dist += ins->x - x + ins->y - y;
		return c[child];
	}
};

int n;
Node *root = new Node();

void dfs(Node *curr) {
	ans = min(ans, tot_dist);
	for (int i = 0; i < 2; i++) {
		if (curr->c[i] != NULL) {
			long long dx = curr->x - curr->c[i]->x + curr->y - curr->c[i]->y;
			tot_dist += dx * (2 * curr->c[i]->l - n);
			dfs(curr->c[i]);
			tot_dist -= dx * (2 * curr->c[i]->l - n);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		Node *curr = root;
		int x, y, cx = 0, cy = 0;
		cin >> x >> y;
		for (int j = 30; ~j; j--) {
			if (x & (1 << j)) {
				cx |= (1 << j);
				curr = curr->insert(new Node(cx, cy), 0);
			}
			if (y & (1 << j)) {
				cy |= (1 << j);
				curr = curr->insert(new Node(cx, cy), 1);
			}
		}
		curr->l++;
	}
	dfs(root);
	cout << ans;
}

Compilation message

cvenk.cpp: In constructor 'Node::Node(int, int)':
cvenk.cpp:7:12: warning: 'Node::l' will be initialized after [-Wreorder]
  int x, y, l;
            ^
cvenk.cpp:7:6: warning:   'int Node::x' [-Wreorder]
  int x, y, l;
      ^
cvenk.cpp:10:2: warning:   when initialized here [-Wreorder]
  Node(int X = 0, int Y = 0): l(0), x(X), y(Y) {
  ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 223 ms 26212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2410 ms 93160 KB Output isn't correct
2 Halted 0 ms 0 KB -