Submission #1416646
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 = 1e12; 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 - cc - i]; 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 | 100 |
Code Size | 2264 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | nonloop | loop | ||||
---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 70 / 70 | ||||
Status |
|
|
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 | AC | 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 | AC | 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 | AC | 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 | AC | 1 ms | 256 KB |
loop/case_033.txt | AC | 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 | AC | 1 ms | 256 KB |
loop/loop_case_008.txt | AC | 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 | AC | 1 ms | 256 KB |
loop/loop_case_013.txt | AC | 1 ms | 256 KB |
loop/loop_case_014.txt | AC | 1 ms | 256 KB |
loop/loop_case_015.txt | AC | 1 ms | 256 KB |
loop/loop_case_016.txt | AC | 1 ms | 256 KB |
loop/loop_case_017.txt | AC | 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 | AC | 1 ms | 256 KB |
loop/loop_case_021.txt | AC | 1 ms | 256 KB |
loop/loop_case_022.txt | AC | 1 ms | 256 KB |
loop/loop_case_023.txt | AC | 1 ms | 256 KB |
loop/loop_case_024.txt | AC | 1 ms | 256 KB |
loop/loop_case_025.txt | AC | 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 | AC | 1 ms | 256 KB |
loop/loop_case_029.txt | AC | 1 ms | 256 KB |
loop/loop_case_030.txt | AC | 1 ms | 256 KB |
loop/loop_case_031.txt | AC | 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 | AC | 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 | AC | 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 | AC | 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 | AC | 1 ms | 256 KB |
nonloop/case_033.txt | AC | 1 ms | 256 KB |