#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
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]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
292 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
2 ms |
344 KB |
Output is correct |
| 8 |
Correct |
8 ms |
596 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
10 ms |
212 KB |
Output is correct |
| 15 |
Correct |
6 ms |
212 KB |
Output is correct |
| 16 |
Correct |
188 ms |
360 KB |
Output is correct |
| 17 |
Correct |
189 ms |
348 KB |
Output is correct |
| 18 |
Correct |
172 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1588 ms |
596 KB |
Output is correct |
| 20 |
Correct |
1616 ms |
596 KB |
Output is correct |
