Submission #1609208
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef unsigned __int128 HASH; typedef pair<int,int> pii; typedef pair<ll, ll> pll; typedef pair<ull, ull> pullull; typedef pair<ll,int> plli; typedef pair<double, int> pdbi; typedef pair<int,pii> pipii; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<pii> vpii; typedef vector<vector<int>> mat; #define rep(i,n) for (int i=0;i<(n);i++) #define rep2(i,a,b) for (int i=(a);i<(b);i++) #define rrep(i,n) for (int i=(n);i>0;i--) #define rrep2(i,a,b) for (int i=(a);i>b;i--) #define pb push_back #define fi first #define se second #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() const ll hmod1 = 999999937; const ll hmod2 = 1000000000 + 9; const ll INF = 1<<30; const ll mod = 1000000000 + 7; const int dx4[4] = {1, 0, -1, 0}; const int dy4[4] = {0, 1, 0, -1}; const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1}; const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1}; const double pi = 3.141592653589793; //#define int long long #define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod int n, m, k; struct edge {int cost, u, v;}; bool comp(const edge& e1, const edge& e2) { return e1.cost > e2.cost; } vector<edge> e; class UnionFind { public: vector<int> parent,rank,tree_w; int tree_cnt; UnionFind(int size) { tree_cnt = size; for (int i = 0; i < size; i++) { parent.push_back(i); rank.push_back(0); tree_w.push_back(1); } } int findset(int x) { return x == parent[x] ? x : parent[x] = findset(parent[x]); } void unite(int x, int y) { x = findset(x); y = findset(y); if (x == y) return; if (rank[x] > rank[y]) swap(x, y); parent[x] = y; tree_cnt -= 1; tree_w[y] += tree_w[x]; if (rank[x] == rank[y]) rank[y] += 1; } bool same(int x, int y) { return findset(x) == findset(y); } int tree_count(){ return tree_cnt; } int tree_weight(int x){ return tree_w[findset(x)]; } }; signed main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> n >> m >> k; ll sum = 0; ll costs = 0; rep(i, m) { int f, t, c; cin >> f >> t >> c; f--; t--; sum += c; e.push_back(edge{c, f, t}); } sort(e.rbegin(), e.rend(), comp); int cnt = n; UnionFind uf (n); int i = 0; ll ans = LLONG_MAX; while (cnt >= k && i < m) { ans = min(ans, sum - costs); uf.unite(e[i].u, e[i].v); cnt = uf.tree_count(); costs += e[i].cost; i++; } if (cnt >= k) ans = min(ans, sum - costs); cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | E - 独立記念日 |
User | roto_37 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3052 Byte |
Status | WA |
Exec Time | 1 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 | 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 | WA | 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 | WA | 1 ms | 256 KB |
loop/case_015.txt | WA | 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 | WA | 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 | WA | 1 ms | 256 KB |
loop/case_026.txt | WA | 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 | WA | 1 ms | 256 KB |
loop/case_031.txt | WA | 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 | WA | 1 ms | 256 KB |
loop/loop_case_002.txt | AC | 1 ms | 256 KB |
loop/loop_case_003.txt | WA | 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 | 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 | WA | 1 ms | 256 KB |
loop/loop_case_011.txt | WA | 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 | WA | 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 | 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 | WA | 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 | WA | 1 ms | 256 KB |
nonloop/case_015.txt | WA | 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 | WA | 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 | WA | 1 ms | 256 KB |
nonloop/case_026.txt | WA | 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 | WA | 1 ms | 256 KB |
nonloop/case_031.txt | WA | 1 ms | 256 KB |
nonloop/case_032.txt | AC | 1 ms | 256 KB |
nonloop/case_033.txt | AC | 1 ms | 256 KB |