QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#770341 | #6619. Line Graph Matching | lonelywolf# | WA | 197ms | 36516kb | C++20 | 1.9kb | 2024-11-21 21:30:03 | 2024-11-21 21:30:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> adj(n + 1);
vector<tuple<int, int, int>> e;
map<pair<int, int>, int> t;
int sum = 0;
for (int i = 1; i <= m; i++) {
int x, y, w;
cin >> x >> y >> w;
sum += w;
t[{x, y}] = w;
t[{y, x}] = w;
e.push_back({x, y, w});
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
if (m % 2 == 0) {
cout << sum << "\n";
return 0;
}
vector<int> low(n + 1), dfn(n + 1), fa(n + 1);
vector<int> cnt(n + 1);
set<pair<int, int>> br;
int tim = 0;
function<void(int, int)> dfs = [&](int x, int f) {
fa[x] = f;
low[x] = dfn[x] = ++tim;
for (auto [y, w] : adj[x]) {
if (!dfn[y]) {
dfs(y, x);
low[x] = min(low[x], low[y]);
if (low[y] > dfn[x]) {
br.insert({x, y});
}
} else if (dfn[y] < dfn[x] && y != f) {
low[x] = min(low[x], dfn[y]);
}
}
};
dfs(1, 0);
vector<int> a(n + 2);
for (int i = 1; i <= n; i++) {
a[low[i]] += adj[i].size();
}
// for (int i = 1; i <= n; i++) {
// cout << a[i] << " \n"[i == n];
// }
for (int i = n; i >= 0; i--) {
a[i] += a[i + 1];
}
for (int i = 0; i <= n; i++) {
a[i] = (a[i] - 1) / 2;
}
// for (int i = 1; i <= n; i++) {
// cout << dfn[i] << " \n"[i == n];
// }
// for (int i = 1; i <= n; i++) {
// cout << low[i] << " \n"[i == n];
// }
// for (int i = 1; i <= n; i++) {
// cout << a[i] << " \n"[i == n];
// }
int mn = 1e18;
for (auto [x, y, w] : e) {
if (!br.count({x, y}) && !br.count({y, x})) {
mn = min(mn, w);
} else {
if (br.count({x, y})) {
if (a[dfn[x] + 1] % 2 == 0) {
mn = min(mn, w);
}
} else {
if (a[dfn[y] + 1] % 2 == 0) {
mn = min(mn, w);
}
}
}
}
cout << sum - mn << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3636kb
input:
5 6 1 2 1 1 3 2 1 4 3 4 3 4 4 5 5 2 5 6
output:
21
result:
ok 1 number(s): "21"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
6 5 1 2 4 2 3 1 3 4 3 4 5 2 5 6 5
output:
12
result:
ok 1 number(s): "12"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
5 5 1 2 1 2 3 2 3 4 3 4 5 4 5 1 5
output:
14
result:
ok 1 number(s): "14"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3 2 1 2 1 2 3 2
output:
3
result:
ok 1 number(s): "3"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
3 3 1 2 3 2 3 1 3 1 2
output:
5
result:
ok 1 number(s): "5"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
6 7 1 2 1 2 3 2 3 4 3 4 1 4 4 5 5 5 6 6 6 4 7
output:
27
result:
ok 1 number(s): "27"
Test #7:
score: -100
Wrong Answer
time: 197ms
memory: 36516kb
input:
100000 99999 54273 5761 179909546 6472 21601 924153552 610 22693 767540137 37784 2454 951330587 24457 93770 781030280 36098 27 448166069 21292 43394 244510129 58047 86330 869927899 18770 83124 20504174 24036 92856 8370757 92492 21932 734860719 43776 77624 226721931 15746 70738 429430538 71204 87185 ...
output:
49946352897973
result:
wrong answer 1st numbers differ - expected: '49946352904479', found: '49946352897973'