Submission #1416733
Source Code Expand
#include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef long long int ll; typedef vector<int> VI; typedef vector<ll> VL; typedef pair<int, int> PI; /* * Union-Find tree * header requirement: vector */ class UnionFind { private: std::vector<int> disj; std::vector<int> rank; public: UnionFind(int n) : disj(n), rank(n) { for (int i = 0; i < n; ++i) { disj[i] = i; rank[i] = 0; } } int root(int x) { if (disj[x] == x) { return x; } return disj[x] = root(disj[x]); } void unite(int x, int y) { x = root(x); y = root(y); if (x == y) { return; } if (rank[x] < rank[y]) { disj[x] = y; } else { disj[y] = x; if (rank[x] == rank[y]) { ++rank[x]; } } } bool is_same_set(int x, int y) { return root(x) == root(y); } }; int main(void) { ios::sync_with_stdio(false); cin.tie(0); int n, m, k; cin >> n >> m >> k; UnionFind uf(n); int conn = n; VI cs; // Assume graph is a tree REP(i, 0, m) { int f, t, c; cin >> f >> t >> c; cs.push_back(c); if (not uf.is_same_set(f, t)) { conn--; } uf.unite(f, t); } sort(cs.begin(), cs.end()); int tot = 0; REP(i, 0, k - conn) { tot += cs[i]; } cout << tot << "\n"; }
Submission Info
Submission Time | |
---|---|
Task | E - 独立記念日 |
User | kobae964 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1728 Byte |
Status | RE |
Exec Time | 102 ms |
Memory | 256 KB |
Judge Result
Set Name | nonloop | loop | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 30 | 0 / 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 | RE | 99 ms | 256 KB |
loop/case_005.txt | RE | 98 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 | RE | 98 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 | RE | 100 ms | 256 KB |
loop/case_017.txt | AC | 1 ms | 256 KB |
loop/case_018.txt | RE | 98 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 | WA | 1 ms | 256 KB |
loop/loop_case_001.txt | WA | 1 ms | 256 KB |
loop/loop_case_002.txt | WA | 1 ms | 256 KB |
loop/loop_case_003.txt | AC | 1 ms | 256 KB |
loop/loop_case_004.txt | WA | 1 ms | 256 KB |
loop/loop_case_005.txt | WA | 1 ms | 256 KB |
loop/loop_case_006.txt | RE | 99 ms | 256 KB |
loop/loop_case_007.txt | RE | 98 ms | 256 KB |
loop/loop_case_008.txt | RE | 101 ms | 256 KB |
loop/loop_case_009.txt | AC | 1 ms | 256 KB |
loop/loop_case_010.txt | WA | 1 ms | 256 KB |
loop/loop_case_011.txt | WA | 1 ms | 256 KB |
loop/loop_case_012.txt | AC | 1 ms | 256 KB |
loop/loop_case_013.txt | RE | 101 ms | 256 KB |
loop/loop_case_014.txt | RE | 99 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 | WA | 1 ms | 256 KB |
loop/loop_case_021.txt | RE | 99 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 | WA | 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 | WA | 1 ms | 256 KB |
loop/loop_case_029.txt | RE | 98 ms | 256 KB |
loop/loop_case_030.txt | RE | 97 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 | RE | 101 ms | 256 KB |
nonloop/case_005.txt | RE | 97 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 | RE | 100 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 | RE | 99 ms | 256 KB |
nonloop/case_017.txt | AC | 1 ms | 256 KB |
nonloop/case_018.txt | RE | 102 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 |