#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;
}
pair<int, int> apm(int n, int m, int alfa, int beta) {
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;
}
}
return rez;
}
long long costfinal = 1000000000000000000LL;
pair<int, int> coef;
map<pair<int, int>, bool> puncte;
void solve(int n, int m, pair<int, int>st, pair<int, int>dr) {
pair<int, int> mid = apm(n, m, st.first - dr.first, dr.second - st.second);
if((long long)mid.first * mid.second < costfinal) {
costfinal = (long long)mid.first * mid.second;
coef.first = st.first - dr.first;
coef.second = dr.second - st.second;
}
if(!puncte[mid]) {
puncte[mid] = true;
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, 0, 1);
dr = apm(n, m, 1, 0);
if((long long)st.first * st.second < costfinal) {
costfinal = (long long)st.first * st.second;
coef.first = 0;
coef.second = 1;
}
if((long long)dr.first * dr.second < costfinal) {
costfinal = (long long)dr.first * dr.second;
coef.first = 1;
coef.second = 0;
}
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:83: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:85: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 |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
524 KB |
Output is correct |
| 4 |
Correct |
3 ms |
524 KB |
Output is correct |
| 5 |
Correct |
3 ms |
524 KB |
Output is correct |
| 6 |
Correct |
5 ms |
524 KB |
Output is correct |
| 7 |
Correct |
108 ms |
816 KB |
Output is correct |
| 8 |
Execution timed out |
2060 ms |
1284 KB |
Time limit exceeded |
| 9 |
Correct |
2 ms |
1284 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1284 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1284 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1284 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1284 KB |
Output is correct |
| 14 |
Correct |
19 ms |
1284 KB |
Output is correct |
| 15 |
Correct |
13 ms |
1284 KB |
Output is correct |
| 16 |
Correct |
308 ms |
1284 KB |
Output is correct |
| 17 |
Correct |
311 ms |
1284 KB |
Output is correct |
| 18 |
Correct |
331 ms |
1284 KB |
Output is correct |
| 19 |
Execution timed out |
2085 ms |
1548 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2072 ms |
1804 KB |
Time limit exceeded |
