#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
struct Line {
int u, v;
ll t, c;
} lines[10000];
bool operator<(Line A, Line B) { return A.t + A.c < B.t + B.c; }
int cmp[200];
int find(int A) {
while (A != cmp[A]) cmp[A] = cmp[cmp[A]], A = cmp[A];
return A;
}
void onion(int A, int B) { cmp[find(A)] = cmp[find(B)]; }
set<Line> graph[200];
bool has_cycle[200];
vector<Line> in_cycle;
void dfs(int target, int node, int parent = -1) {
if (node == target) {
has_cycle[node] = true;
return;
}
for (Line i : graph[node]) {
if (i.u != parent && i.v != parent) {
dfs(target, node == i.u ? i.v : i.u, node);
if (has_cycle[node == i.u ? i.v : i.u]) {
in_cycle.push_back(i);
has_cycle[node] = true;
return;
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
FOR(i, 0, m) cin >> lines[i].u >> lines[i].v >> lines[i].t >> lines[i].c;
sort(lines, lines + m);
iota(cmp, cmp + n, 0);
set<Line> res;
ll t = 0, c = 0;
FOR(i, 0, m) {
if (find(lines[i].u) != find(lines[i].v)) {
t += lines[i].t, c += lines[i].c;
onion(lines[i].u, lines[i].v);
res.insert(lines[i]);
graph[lines[i].u].insert(lines[i]);
graph[lines[i].v].insert(lines[i]);
} else {
fill(has_cycle, has_cycle + n, false);
in_cycle.clear();
dfs(lines[i].u, lines[i].v);
ll best = t * c;
Line to_remove = lines[i];
for (Line j : in_cycle) {
if ((t - j.t + lines[i].t) * (c - j.c + lines[i].c) < best) {
best = (t - j.t + lines[i].t) * (c - j.c + lines[i].c);
to_remove = j;
}
}
if (best != t * c) {
res.erase(to_remove);
res.insert(lines[i]);
graph[to_remove.u].erase(to_remove);
graph[to_remove.v].erase(to_remove);
graph[lines[i].u].insert(lines[i]);
graph[lines[i].v].insert(lines[i]);
t += lines[i].t - to_remove.t;
c += lines[i].c - to_remove.c;
}
}
}
cout << t << ' ' << c << '\n';
for (Line i : res) cout << i.u << ' ' << i.v << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Unexpected end of file - int32 expected |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
5 ms |
384 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
5 ms |
384 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
9 ms |
384 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
14 ms |
640 KB |
Unexpected end of file - int32 expected |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Incorrect |
4 ms |
384 KB |
Unexpected end of file - int32 expected |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Incorrect |
4 ms |
384 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 14 |
Incorrect |
7 ms |
384 KB |
Output isn't correct |
| 15 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 16 |
Incorrect |
11 ms |
384 KB |
Output isn't correct |
| 17 |
Incorrect |
10 ms |
512 KB |
Output isn't correct |
| 18 |
Incorrect |
11 ms |
384 KB |
Output isn't correct |
| 19 |
Incorrect |
31 ms |
640 KB |
Output isn't correct |
| 20 |
Incorrect |
24 ms |
640 KB |
Output isn't correct |
