#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ll cross(pii a, pii b) {
return 1LL * a.first * b.second - a.second * b.first;
}
ll ccw(pii a, pii b, pii c) {
pii p = pii(b.first - a.first, b.second - a.second);
pii q = pii(c.first - a.first, c.second - a.second);
return cross(p, q);
}
int N, M, T, C;
struct Edge {
int u, v, t, c;
};
Edge edge[10010];
vector<pii> sol, tmp;
bool cmp(Edge a, Edge b) {
return 1LL * T * a.t + 1LL * C * a.c < 1LL * T * b.t + 1LL * C * b.c;
}
struct DSU {
int par[202], rnk[202];
void init() {
for(int i = 0; i < N; i++) {
par[i] = i;
rnk[i] = 0;
}
}
int f(int u) {
if(par[u] == u) return u;
else return par[u] = f(par[u]);
}
void mrg(int u, int v) {
u = f(u);
v = f(v);
if(u == v) return;
if(rnk[u] < rnk[v]) swap(u, v);
par[v] = u;
if(rnk[u] == rnk[v]) rnk[u]++;
}
} dsu;
pii solve(int a, int b) {
T = a;
C = b;
sort(edge, edge + M, cmp);
pii ret = pii(0, 0);
dsu.init();
tmp.clear();
for(int i = 0; i < M; i++) {
int u = edge[i].u;
int v = edge[i].v;
int t = edge[i].t;
int c = edge[i].c;
if(dsu.f(u) == dsu.f(v)) continue;
dsu.mrg(u, v);
ret.first += t;
ret.second += c;
tmp.push_back(pii(u, v));
}
return ret;
}
pii ans = pii(1e9, 1e9);
void rec(pii s, pii e) {
int a = e.first - s.first;
int b = s.second - e.second;
pii m = solve(a, b);
if(ccw(s, m, e) > 0) {
if(1LL * ans.first * ans.second > 1LL * m.first * m.second) {
ans = m;
sol = tmp;
}
rec(s, m);
rec(m, e);
}
}
int main() {
scanf("%d %d", &N, &M);
for(int i = 0; i < M; i++) {
int u, v, t, c; scanf("%d %d %d %d", &u, &v, &t, &c);
edge[i] = {u, v, t, c};
}
pii s = solve(1, 0);
if(1LL * ans.first * ans.second > 1LL * s.first * s.second) {
ans = s;
sol = tmp;
}
pii e = solve(0, 1);
if(1LL * ans.first * ans.second > 1LL * e.first * e.second) {
ans = e;
sol = tmp;
}
rec(s, e);
printf("%d %d\n", ans.first, ans.second);
for(int i = 0; i < sol.size(); i++) {
printf("%d %d\n", sol[i].first, sol[i].second);
}
}
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:113:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < sol.size(); i++) {
^
timeismoney.cpp:91:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
^
timeismoney.cpp:94:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v, t, c; scanf("%d %d %d %d", &u, &v, &t, &c);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
248 KB |
Output is correct |
| 2 |
Correct |
1 ms |
352 KB |
Output is correct |
| 3 |
Correct |
1 ms |
352 KB |
Output is correct |
| 4 |
Correct |
1 ms |
408 KB |
Output is correct |
| 5 |
Correct |
2 ms |
408 KB |
Output is correct |
| 6 |
Correct |
2 ms |
460 KB |
Output is correct |
| 7 |
Correct |
2 ms |
476 KB |
Output is correct |
| 8 |
Correct |
7 ms |
660 KB |
Output is correct |
| 9 |
Correct |
1 ms |
660 KB |
Output is correct |
| 10 |
Correct |
1 ms |
660 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
660 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
660 KB |
Output isn't correct |
| 13 |
Incorrect |
1 ms |
660 KB |
Output isn't correct |
| 14 |
Incorrect |
2 ms |
660 KB |
Output isn't correct |
| 15 |
Correct |
2 ms |
660 KB |
Output is correct |
| 16 |
Incorrect |
5 ms |
660 KB |
Output isn't correct |
| 17 |
Incorrect |
4 ms |
660 KB |
Output isn't correct |
| 18 |
Incorrect |
4 ms |
660 KB |
Output isn't correct |
| 19 |
Incorrect |
11 ms |
748 KB |
Output isn't correct |
| 20 |
Incorrect |
11 ms |
852 KB |
Output isn't correct |
