QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#615066 | #8941. Even or Odd Spanning Tree | m107239# | RE | 0ms | 3792kb | C++20 | 3.0kb | 2024-10-05 17:32:37 | 2024-10-05 17:32:38 |
Judging History
answer
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<tuple<int, int, int>> edge(m);
vector<bool> chose(m);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
edge[i] = {w, u, v};
}
sort(edge.begin(), edge.end());
vector<int> p(n);
iota(p.begin(), p.end(), 0);
auto find = [&](int x) {
while (x != p[x]) {
x = p[x] = p[p[x]];
}
return x;
};
vector<vector<pair<int, int>>> adj(n);
ll sum = 0;
for (int i = 0; i < m; i++) {
auto [w, u, v] = edge[i];
int x = find(u), y = find(v);
if (x != y) {
sum += w;
p[y] = x;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
chose[i] = true;
}
}
for (int i = 0; i < n; i++) {
if (find(i) != find(0)) {
cout << -1 << " " << -1 << endl;
return;
}
}
vector<array<int, 20>> fa(n);
vector<array<array<int, 20>, 2>> we(n);
vector<int> dep(n);
auto dfs = [&](auto &&self, int u) -> void {
for (int i = 1; i < 20; i++) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
we[0][u][i] = max(we[0][u][i], we[0][we[0][u][i - 1]][i - 1]);
we[1][u][i] = max(we[1][u][i], we[1][we[1][u][i - 1]][i - 1]);
}
for (auto [v, w] : adj[u]) {
if (v != fa[u][0]) {
we[w & 1][v][0] = w;
fa[v][0] = u;
dep[v] = dep[u] + 1;
self(self, v);
}
}
};
dfs(dfs, 0);
auto LCA = [&](int x, int y, int k) {
if (dep[x] < dep[y]) {
swap(x, y);
}
int ans = 0;
for (int i = 19; i >= 0; i--) {
if (dep[fa[x][i]] >= dep[y]) {
x = fa[x][i];
ans = max(ans, we[k][x][i]);
}
}
if (x == y) return ans;
for (int i = 19; i >= 0; i--) {
if (fa[x][i] != fa[y][i]) {
ans = max(ans, we[k][x][i]);
ans = max(ans, we[k][y][i]);
x = fa[x][i];
y = fa[y][i];
}
}
return max(ans, we[k][x][0]);
};
ll ans = 1e18;
for (int i = 0; i < m; i++) {
if (!chose[i]) {
auto [w, x, y] = edge[i];
int res = LCA(x, y, ~w & 1);
if (res != 0) {
ans = min(ans, sum - res + w);
}
}
}
if (sum & 1) {
cout << ((ans == 1e18) ? -1 : ans) << " " << sum << endl;
} else {
cout << sum << " " << ((ans == 1e18) ? -1 : ans) << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3792kb
input:
3 2 1 1 2 5 3 1 1 3 1 4 4 1 2 1 1 3 1 1 4 1 2 4 2
output:
-1 5 -1 -1 4 3
result:
ok 6 numbers
Test #2:
score: -100
Runtime Error
input:
10000 16 50 1 2 649251632 2 3 605963017 3 4 897721528 4 5 82446151 5 6 917109168 6 7 79647183 7 8 278566178 7 9 573504723 3 10 679859251 8 11 563113083 1 12 843328546 10 13 594049160 11 14 997882839 7 15 569431750 2 16 244494799 16 7 960172373 13 4 317888322 13 3 446883598 9 3 678142319 5 8 43208692...