QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#615066#8941. Even or Odd Spanning Treem107239#RE 0ms3792kbC++203.0kb2024-10-05 17:32:372024-10-05 17:32:38

Judging History

你现在查看的是最新测评结果

  • [2024-10-05 17:32:38]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3792kb
  • [2024-10-05 17:32:37]
  • 提交

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...

output:


result: