oj.uz

답안 #26000

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26000 2017-06-25T17:40:23 Z abcdef6199 도로 건설 사업 (JOI13_construction) C++
40 / 100
 5000 ms 26244 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> II;
struct Point {
	int x, y, i;
	Point() {};
	Point(int x, int y, int i): x(x), y(y), i(i) {};
};
struct Edge {
	int u, v, w;
	Edge() {};
	Edge(int u, int v, int w): u(u), v(v), w(w) {};
	bool operator < (const Edge &E) const {
		return w < E.w;
	}
};

const int N = (int) 2e5 + 10;
int n, m, k, q, x[N], y[N];
Point P[N];
Edge E[N * 4];
bool mark[N * 4];

int p[N];
int com_count[N * 4];
LL  sum_edges[N * 4];

int Root(int u) {
	if (p[u] < 0) return u;
	return p[u] = Root(p[u]);
}

int Merge(int u, int v) {
	u = Root(u);
	v = Root(v);
	if (u == v) return 0;
	if (p[u] > p[v]) swap(u, v);
	p[u] += p[v]; p[v] = u;
	return 1;
}

bool cmp_by_X(Point A, Point B) { return A.x < B.x || (A.x == B.x && A.y < B.y); }
bool cmp_by_Y(Point A, Point B) { return A.y < B.y || (A.y == B.y && A.x < B.x); }

void InitEdge() {
	sort(P + 1, P + 1 + n, cmp_by_X);
	for (int i = 1; i <= n; ++i) {
		int j = i;
		while (j < n && P[j + 1].x == P[i].x) j++;
		for (int t = i; t <= j - 1; ++t) {
			int w = abs(P[t].x - P[t + 1].x) + abs(P[t].y - P[t + 1].y);
			E[++m] = Edge(P[t].i, P[t + 1].i, w);
		}
		i = j;
	}
	sort(P + 1, P + 1 + n, cmp_by_Y);
	for (int i = 1; i <= n; ++i) {
		int j = i;
		while (j < n && P[j + 1].y == P[i].y) j++;
		for (int t = i; t <= j - 1; ++t) {
			int w = abs(P[t].x - P[t + 1].x) + abs(P[t].y - P[t + 1].y);
			E[++m] = Edge(P[t].i, P[t + 1].i, w);
		}
		i = j;
	}
	sort(E + 1, E + 1 + m);
}

int main() {
	scanf("%d%d%d", &n, &k, &q);
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d", &x[i], &y[i]);
		P[i] = Point(x[i], y[i], i);
	}
	InitEdge();

	for (int i = 1; i <= m; ++i) mark[i] = true;
	for (int i = 1; i <= k; ++i) {
		int x1, y1; scanf("%d%d", &x1, &y1);
		int x2, y2; scanf("%d%d", &x2, &y2);
		for (int j = 1; j <= m; ++j) {
			int u = E[j].u;
			int v = E[j].v;
			if (x[u] == x[v] && x1 <= x[u] && x[u] <= x2) {
				if (max(y[u], y1) <= min(y[v], y2)) mark[j] = false;
			}
			if (y[u] == y[v] && y1 <= y[u] && y[u] <= y2) {
				if (max(x[u], x1) <= min(x[v], x2)) mark[j] = false;
			}
		}
	}

	for (int i = 1; i <= n; ++i) p[i] = -1; com_count[0] = n;
	for (int i = 1; i <= m; ++i) {
		int u = E[i].u;
		int v = E[i].v;
		com_count[i] = com_count[i - 1];
		sum_edges[i] = sum_edges[i - 1];
		if (mark[i] && Merge(u, v)) {
			com_count[i] -= 1;
			sum_edges[i] += E[i].w;
		}
	}

	while (q--) {
		int a, b; scanf("%d%d", &a, &b);
		int l = 1, r = m, f = -1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (com_count[mid] <= b) {
				f = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		LL ans = (LL) 1e18;
		if (f != -1) ans = min(ans, sum_edges[f] + (LL) a * b);

		l = 1; r = m; f = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (E[mid].w <= a) {
				f = mid;
				l = mid + 1;
			}
			else r = mid - 1;
		}
		if (com_count[f] <= b) ans = min(ans, sum_edges[f] + (LL) a * com_count[f]);
		if (ans == (LL) 1e18) ans = -1;
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:72:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
                             ^
construction.cpp:74:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x[i], &y[i]);
                              ^
construction.cpp:81:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x1, y1; scanf("%d%d", &x1, &y1);
                                      ^
construction.cpp:82:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x2, y2; scanf("%d%d", &x2, &y2);
                                      ^
construction.cpp:108:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
                                  ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 366 ms 26244 KB Output is correct
2 Correct 579 ms 26244 KB Output is correct
3 Correct 659 ms 26244 KB Output is correct
4 Correct 909 ms 26244 KB Output is correct
5 Correct 169 ms 26244 KB Output is correct
6 Correct 616 ms 26244 KB Output is correct
7 Correct 276 ms 26244 KB Output is correct
8 Correct 386 ms 26244 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5000 ms 26244 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1053 ms 26244 KB Output is correct
2 Correct 1203 ms 26244 KB Output is correct
3 Correct 1022 ms 26244 KB Output is correct
4 Correct 1493 ms 26244 KB Output is correct
5 Correct 833 ms 26244 KB Output is correct
6 Correct 686 ms 26244 KB Output is correct
7 Correct 1079 ms 26244 KB Output is correct
8 Correct 1006 ms 26244 KB Output is correct
9 Correct 669 ms 26244 KB Output is correct
10 Correct 809 ms 26244 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5000 ms 26244 KB Execution timed out
2 Halted 0 ms 0 KB -