Submission #728022

#	Time	Username	Problem	Language	Result	Execution time	Memory
728022		rainboy	timeismoney (balkan11_timeismoney)	C11	100 / 100	1616 ms	596 KiB

timeismoney

#include <stdio.h>
#include <string.h>

#define N	200
#define M	10000

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int n;

int ii[M], jj[M], xx[M], yy[M], hh[M], m;

int a1, b1;

int compare(int h1, int h2) {
	long long z1 = (long long) a1 * xx[h1] + (long long) b1 * yy[h1];
	long long z2 = (long long) a1 * xx[h2] + (long long) b1 * yy[h2];

	if (z1 != z2)
		return z1 < z2 ? -1 : 1;
	return xx[h1] != xx[h2] ? xx[h1] - xx[h2] : yy[h2] - yy[h1];
}

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(hh[j], h);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

int ds[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

int join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}

void solve(int a, int b, int *x, int *y, int print) {
	int h, h_;

	a1 = a, b1 = b;
	for (h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	memset(ds, -1, n * sizeof *ds);
	*x = *y = 0;
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		if (join(ii[h_], jj[h_])) {
			if (print)
				printf("%d %d\n", ii[h_], jj[h_]);
			*x += xx[h_], *y += yy[h_];
		}
	}
}

long long z_; int x_, y_, a_, b_;

void enumerate(int x1, int y1, int x2, int y2) {
	int x, y;
	long long z;

	solve(y1 - y2, x2 - x1, &x, &y, 0);
	if (x != x1 || y != y1)
		enumerate(x1, y1, x, y), enumerate(x, y, x2, y2);
	else {
		z = (long long) x1 * y1;
		if (z_ > z)
			z_ = z, x_ = x1, y_ = y1, a_ = y1 - y2, b_ = x2 - x1;
	}
}

int main() {
	int h, x1, y1, x2, y2;

	scanf("%d%d", &n, &m);
	for (h = 0; h < m; h++)
		scanf("%d%d%d%d", &ii[h], &jj[h], &xx[h], &yy[h]);
	solve(1, 0, &x1, &y1, 0);
	solve(0, 1, &x2, &y2, 0);
	z_ = (long long) x2 * y2, x_ = x2, y_ = y2, a_ = 0, b_ = 1;
	enumerate(x1, y1, x2, y2);
	printf("%d %d\n", x_, y_);
	solve(a_, b_, &x_, &y_, 1);
	return 0;
}

Compilation message (stderr)

timeismoney.c: In function 'main':
timeismoney.c:109:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
timeismoney.c:111:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%d%d%d%d", &ii[h], &jj[h], &xx[h], &yy[h]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100