Submission #1416639


Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

int input() {
    int n;
    std::cin >> n;
    return n;
}

struct edge { int v, w; };

struct DSU {
    std::vector<int> par;

    DSU(int n) : par(n) {
        for (int i = 0; i < n; i++) {
            par[i] = i;
        }
    }

    int find(int x) {
        if (par[x] == x) return x;
        return par[x] = find(par[x]);
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        par[x] = y;
        return true;
    }
};

int main() {
    int n, m, K;
    std::cin >> n >> m >> K;

    std::vector<std::vector<edge>> g(n);
    std::vector<int> deg(n);
    DSU dsu(n);

    int cc = n;

    for (int i = 0; i < m; i++) {
        int u = input() - 1;
        int v = input() - 1;
        int w = input();

        deg[u]++;
        deg[v]++;
        cc -= dsu.unite(u, v);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    std::vector<bool> cycle(n, true);
    std::queue<int> q;
    for (int i = 0; i < n; i++) {
        if (deg[i] == 1) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cycle[u] = false;
        for (edge e : g[u]) {
            if (--deg[e.v] == 1) {
                q.push(e.v);
            }
        }
    }

    std::vector<long long> a, b;

    for (int i = 0; i < n; i++) {
        for (edge e : g[i]) {
            int j = e.v;
            if (i >= j) continue;
            if (cycle[i] && cycle[j]) {
                b.push_back(e.w);
            } else {
                a.push_back(e.w);
            }
        }
    }

    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    constexpr long long INF = 1e18;
    a.resize(K + 2, INF);
    b.resize(K + 2, INF);
    long long sum = 0;
    for (int i = 0; i < K - cc; i++) {
        sum += a[i];
    }

    long long ans = sum;
    sum += b[0];

    for (int i = 1; i <= K - cc; i++) {
        sum -= a[K - 2];
        sum += b[i];
        ans = std::min(ans, sum);
    }

    std::cout << ans << std::endl;
}

Submission Info

Submission Time
Task E - 独立記念日
User pekempey
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2259 Byte
Status WA
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name nonloop loop
Score / Max Score 0 / 30 0 / 70
Status
AC × 29
WA × 5
AC × 47
WA × 19
Set Name Test Cases
nonloop nonloop/case_000.txt, nonloop/case_001.txt, nonloop/case_002.txt, nonloop/case_003.txt, nonloop/case_004.txt, nonloop/case_005.txt, nonloop/case_006.txt, nonloop/case_007.txt, nonloop/case_008.txt, nonloop/case_009.txt, nonloop/case_010.txt, nonloop/case_011.txt, nonloop/case_012.txt, nonloop/case_013.txt, nonloop/case_014.txt, nonloop/case_015.txt, nonloop/case_016.txt, nonloop/case_017.txt, nonloop/case_018.txt, nonloop/case_019.txt, nonloop/case_020.txt, nonloop/case_021.txt, nonloop/case_022.txt, nonloop/case_023.txt, nonloop/case_024.txt, nonloop/case_025.txt, nonloop/case_026.txt, nonloop/case_027.txt, nonloop/case_028.txt, nonloop/case_029.txt, nonloop/case_030.txt, nonloop/case_031.txt, nonloop/case_032.txt, nonloop/case_033.txt
loop loop/case_000.txt, loop/case_001.txt, loop/case_002.txt, loop/case_003.txt, loop/case_004.txt, loop/case_005.txt, loop/case_006.txt, loop/case_007.txt, loop/case_008.txt, loop/case_009.txt, loop/case_010.txt, loop/case_011.txt, loop/case_012.txt, loop/case_013.txt, loop/case_014.txt, loop/case_015.txt, loop/case_016.txt, loop/case_017.txt, loop/case_018.txt, loop/case_019.txt, loop/case_020.txt, loop/case_021.txt, loop/case_022.txt, loop/case_023.txt, loop/case_024.txt, loop/case_025.txt, loop/case_026.txt, loop/case_027.txt, loop/case_028.txt, loop/case_029.txt, loop/case_030.txt, loop/case_031.txt, loop/case_032.txt, loop/case_033.txt, loop/loop_case_000.txt, loop/loop_case_001.txt, loop/loop_case_002.txt, loop/loop_case_003.txt, loop/loop_case_004.txt, loop/loop_case_005.txt, loop/loop_case_006.txt, loop/loop_case_007.txt, loop/loop_case_008.txt, loop/loop_case_009.txt, loop/loop_case_010.txt, loop/loop_case_011.txt, loop/loop_case_012.txt, loop/loop_case_013.txt, loop/loop_case_014.txt, loop/loop_case_015.txt, loop/loop_case_016.txt, loop/loop_case_017.txt, loop/loop_case_018.txt, loop/loop_case_019.txt, loop/loop_case_020.txt, loop/loop_case_021.txt, loop/loop_case_022.txt, loop/loop_case_023.txt, loop/loop_case_024.txt, loop/loop_case_025.txt, loop/loop_case_026.txt, loop/loop_case_027.txt, loop/loop_case_028.txt, loop/loop_case_029.txt, loop/loop_case_030.txt, loop/loop_case_031.txt
Case Name Status Exec Time Memory
loop/case_000.txt AC 1 ms 256 KB
loop/case_001.txt AC 1 ms 256 KB
loop/case_002.txt AC 1 ms 256 KB
loop/case_003.txt AC 1 ms 256 KB
loop/case_004.txt WA 1 ms 256 KB
loop/case_005.txt AC 1 ms 256 KB
loop/case_006.txt AC 1 ms 256 KB
loop/case_007.txt AC 1 ms 256 KB
loop/case_008.txt AC 1 ms 256 KB
loop/case_009.txt AC 1 ms 256 KB
loop/case_010.txt AC 1 ms 256 KB
loop/case_011.txt AC 1 ms 256 KB
loop/case_012.txt AC 1 ms 256 KB
loop/case_013.txt AC 1 ms 256 KB
loop/case_014.txt AC 1 ms 256 KB
loop/case_015.txt AC 1 ms 256 KB
loop/case_016.txt WA 1 ms 256 KB
loop/case_017.txt AC 1 ms 256 KB
loop/case_018.txt AC 1 ms 256 KB
loop/case_019.txt AC 1 ms 256 KB
loop/case_020.txt AC 1 ms 256 KB
loop/case_021.txt AC 1 ms 256 KB
loop/case_022.txt AC 1 ms 256 KB
loop/case_023.txt WA 1 ms 256 KB
loop/case_024.txt AC 1 ms 256 KB
loop/case_025.txt AC 1 ms 256 KB
loop/case_026.txt AC 1 ms 256 KB
loop/case_027.txt AC 1 ms 256 KB
loop/case_028.txt AC 1 ms 256 KB
loop/case_029.txt AC 1 ms 256 KB
loop/case_030.txt AC 1 ms 256 KB
loop/case_031.txt AC 1 ms 256 KB
loop/case_032.txt WA 1 ms 256 KB
loop/case_033.txt WA 1 ms 256 KB
loop/loop_case_000.txt AC 1 ms 256 KB
loop/loop_case_001.txt AC 1 ms 256 KB
loop/loop_case_002.txt AC 1 ms 256 KB
loop/loop_case_003.txt AC 1 ms 256 KB
loop/loop_case_004.txt AC 1 ms 256 KB
loop/loop_case_005.txt AC 1 ms 256 KB
loop/loop_case_006.txt AC 1 ms 256 KB
loop/loop_case_007.txt WA 1 ms 256 KB
loop/loop_case_008.txt WA 1 ms 256 KB
loop/loop_case_009.txt AC 1 ms 256 KB
loop/loop_case_010.txt AC 1 ms 256 KB
loop/loop_case_011.txt AC 1 ms 256 KB
loop/loop_case_012.txt WA 1 ms 256 KB
loop/loop_case_013.txt WA 1 ms 256 KB
loop/loop_case_014.txt AC 1 ms 256 KB
loop/loop_case_015.txt WA 1 ms 256 KB
loop/loop_case_016.txt WA 1 ms 256 KB
loop/loop_case_017.txt WA 1 ms 256 KB
loop/loop_case_018.txt AC 1 ms 256 KB
loop/loop_case_019.txt AC 1 ms 256 KB
loop/loop_case_020.txt WA 1 ms 256 KB
loop/loop_case_021.txt AC 1 ms 256 KB
loop/loop_case_022.txt WA 1 ms 256 KB
loop/loop_case_023.txt AC 1 ms 256 KB
loop/loop_case_024.txt WA 1 ms 256 KB
loop/loop_case_025.txt WA 1 ms 256 KB
loop/loop_case_026.txt AC 1 ms 256 KB
loop/loop_case_027.txt AC 1 ms 256 KB
loop/loop_case_028.txt WA 1 ms 256 KB
loop/loop_case_029.txt AC 1 ms 256 KB
loop/loop_case_030.txt WA 1 ms 256 KB
loop/loop_case_031.txt WA 1 ms 256 KB
nonloop/case_000.txt AC 1 ms 256 KB
nonloop/case_001.txt AC 1 ms 256 KB
nonloop/case_002.txt AC 1 ms 256 KB
nonloop/case_003.txt AC 1 ms 256 KB
nonloop/case_004.txt WA 1 ms 256 KB
nonloop/case_005.txt AC 1 ms 256 KB
nonloop/case_006.txt AC 1 ms 256 KB
nonloop/case_007.txt AC 1 ms 256 KB
nonloop/case_008.txt AC 1 ms 256 KB
nonloop/case_009.txt AC 1 ms 256 KB
nonloop/case_010.txt AC 1 ms 256 KB
nonloop/case_011.txt AC 1 ms 256 KB
nonloop/case_012.txt AC 1 ms 256 KB
nonloop/case_013.txt AC 1 ms 256 KB
nonloop/case_014.txt AC 1 ms 256 KB
nonloop/case_015.txt AC 1 ms 256 KB
nonloop/case_016.txt WA 1 ms 256 KB
nonloop/case_017.txt AC 1 ms 256 KB
nonloop/case_018.txt AC 1 ms 256 KB
nonloop/case_019.txt AC 1 ms 256 KB
nonloop/case_020.txt AC 1 ms 256 KB
nonloop/case_021.txt AC 1 ms 256 KB
nonloop/case_022.txt AC 1 ms 256 KB
nonloop/case_023.txt WA 1 ms 256 KB
nonloop/case_024.txt AC 1 ms 256 KB
nonloop/case_025.txt AC 1 ms 256 KB
nonloop/case_026.txt AC 1 ms 256 KB
nonloop/case_027.txt AC 1 ms 256 KB
nonloop/case_028.txt AC 1 ms 256 KB
nonloop/case_029.txt AC 1 ms 256 KB
nonloop/case_030.txt AC 1 ms 256 KB
nonloop/case_031.txt AC 1 ms 256 KB
nonloop/case_032.txt WA 1 ms 256 KB
nonloop/case_033.txt WA 1 ms 256 KB