#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 255;
const int MAX_M = 10000;
struct Muchie {
int a, b, c, d;
int cost;
bool inapm;
}mc[MAX_M];
bool cmp(Muchie a, Muchie b) {
return a.cost < b.cost;
}
int sefu[MAX_N];
int myfind(int x) {
if(x == sefu[x])
return x;
else {
sefu[x] = myfind(sefu[x]);
return sefu[x];
}
}
void myunion(int a, int b) {
int sa = myfind(a), sb = myfind(b);
if(sa != sb)
sefu[sa] = sb;
}
bool ccw(pair<int, int>a, pair<int, int>b, pair<int, int>c) {
return (long long)a.first * b.second +
(long long)b.first * c.second +
(long long)c.first * a.second -
(long long)a.first * c.second -
(long long)b.first * a.second -
(long long)c.first * b.second > 0;
}
pair<int, int> apm(int n, int m, int alfa, int beta) {
int rem = n - 1;
pair<int, int> rez = make_pair(0, 0);
for(int i = 0; i < n; ++i)
sefu[i] = i;
for(int i = 0; i < m; ++i) {
mc[i].cost = mc[i].c * alfa + mc[i].d * beta;
mc[i].inapm = false;
}
sort(mc, mc + m, cmp);
for(int i = 0; i < m; ++i) {
if(myfind(mc[i].a) != myfind(mc[i].b)) {
rez.first += mc[i].c;
rez.second += mc[i].d;
myunion(mc[i].a, mc[i].b);
mc[i].inapm = true;
--rem;
if(rem == 0)
return rez;
}
}
return rez;
}
long long costfinal = 1000000000000000000LL;
pair<int, int> coef;
void solve(int n, int m, pair<int, int>st, pair<int, int>dr) {
pair<int, int> mid = apm(n, m, st.second - dr.second, dr.first - st.first);
if((long long)mid.first * mid.second < costfinal) {
costfinal = (long long)mid.first * mid.second;
coef.first = st.second - dr.second;
coef.second = dr.first - st.first;
}
if(ccw(st, mid, dr)) {
solve(n, m, st, mid);
solve(n, m, mid, dr);
}
}
int main() {
#ifdef HOME
FILE *fin = fopen("timeismoney.in", "r");
FILE *fout = fopen("timeismoney.out", "w");
#else
FILE *fin = stdin;
FILE *fout = stdout;
#endif
int n, m;
fscanf(fin, "%d%d", &n, &m);
for(int i = 0; i < m; ++i)
fscanf(fin, "%d%d%d%d", &mc[i].a, &mc[i].b, &mc[i].c, &mc[i].d);
pair<int, int>st, dr, xd;
st = apm(n, m, 1, 0);
dr = apm(n, m, 0, 1);
if((long long)st.first * st.second < costfinal) {
costfinal = (long long)st.first * st.second;
coef.first = 1;
coef.second = 0;
}
if((long long)dr.first * dr.second < costfinal) {
costfinal = (long long)dr.first * dr.second;
coef.first = 0;
coef.second = 1;
}
solve(n, m, st, dr);
xd = apm(n, m, coef.first, coef.second);
fprintf(fout, "%d %d\n", xd.first, xd.second);
for(int i = 0; i < m; ++i)
if(mc[i].inapm)
fprintf(fout, "%d %d\n", mc[i].a, mc[i].b);
#ifdef HOME
fclose(fin);
fclose(fout);
#endif // HOME
return 0;
}
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:92:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fin, "%d%d", &n, &m);
~~~~~~^~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:94:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fin, "%d%d%d%d", &mc[i].a, &mc[i].b, &mc[i].c, &mc[i].d);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
548 KB |
Output is correct |
| 4 |
Correct |
2 ms |
548 KB |
Output is correct |
| 5 |
Correct |
2 ms |
548 KB |
Output is correct |
| 6 |
Correct |
2 ms |
548 KB |
Output is correct |
| 7 |
Correct |
3 ms |
556 KB |
Output is correct |
| 8 |
Correct |
8 ms |
812 KB |
Output is correct |
| 9 |
Correct |
2 ms |
812 KB |
Output is correct |
| 10 |
Correct |
2 ms |
812 KB |
Output is correct |
| 11 |
Correct |
2 ms |
812 KB |
Output is correct |
| 12 |
Correct |
2 ms |
812 KB |
Output is correct |
| 13 |
Correct |
2 ms |
812 KB |
Output is correct |
| 14 |
Correct |
7 ms |
812 KB |
Output is correct |
| 15 |
Correct |
6 ms |
812 KB |
Output is correct |
| 16 |
Correct |
89 ms |
812 KB |
Output is correct |
| 17 |
Correct |
97 ms |
812 KB |
Output is correct |
| 18 |
Correct |
89 ms |
812 KB |
Output is correct |
| 19 |
Correct |
757 ms |
876 KB |
Output is correct |
| 20 |
Correct |
769 ms |
892 KB |
Output is correct |
