Submission #3449190
Source Code Expand
#include <iostream> #include <vector> using namespace std; using ll = long long; const ll INF = 1LL << 50; const int MAX_V = 100010; class UnionFind { public: // コンストラクタ explicit UnionFind(int N) : V_NUM(N) { for (int i = 0; i < V_NUM; ++i) { par[i] = i; } fill(rank, rank + V_NUM, 0); } // xの親を返す+更新 int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } // xとyを含むグループを統合する void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]) swap(x, y); // rank[x] >= rank[y] // rankの大きい方、つまりxにyをくっつける par[y] = x; if (rank[x] == rank[y]) ++rank[x]; } // xとyが同じグループに属するか判定 bool same(int x, int y) { return find(x) == find(y); } const int INF = 1 << 25; int V_NUM; int par[MAX_V], rank[MAX_V]; }; int main() { int N, M; cin >> N >> M; ll v[N + 1]; ll ans = 0; for (int i = 0; i < N; ++i) { cin >> v[i]; ans += v[i]; } UnionFind uf(N); int x[M], y[M]; for (int i = 0; i < M; ++i) { cin >> x[i] >> y[i]; // xとyを辺で結ぶ uf.unite(--x[i], --y[i]); } int sz[N]; fill(sz, sz + N, 0); // sz[v] = vを親とするグラフが含む辺の本数 for (int i = 0; i < M; ++i) { ++sz[uf.find(x[i])]; } vector<int> child[N]; // child[v] = vを親とするグラフが含む頂点の集合 for (int i = 0; i < N; ++i) { child[uf.find(i)].push_back(i); } for (int i = 0; i < N; ++i) { // 条件: // 1. iがグラフの親である // 2. iを親とするグラフが木である if (i == uf.find(i) && child[i].size() == sz[i] + 1) { // このとき, 木から1つ頂点を選ぶことができなくなる ll del = INF; for (int j : child[i]) { del = min(del, v[j]); } ans -= del; } } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Treasure Hunt |
User | Tiramister |
Language | C++14 (GCC 5.4.1) |
Score | 200 |
Code Size | 2399 Byte |
Status | AC |
Exec Time | 175 ms |
Memory | 7680 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 200 / 200 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_small_n_random0, 00_small_n_random1, 00_small_n_random2, 01_small_1g_random0, 01_small_1g_random1, 01_small_1g_random2, 02_small_mg_random0, 02_small_mg_random1, 02_small_mg_random2, 10_medium_n_random0, 10_medium_n_random1, 10_medium_n_random2, 11_medium_1g_random0, 11_medium_1g_random1, 11_medium_1g_random2, 12_medium_mg_random0, 12_medium_mg_random1, 12_medium_mg_random2, 20_large_n_random0, 20_large_n_random1, 20_large_n_random2, 21_large_1g_random0, 21_large_1g_random1, 21_large_1g_random2, 22_large_mg_random0, 22_large_mg_random1, 22_large_mg_random2, 23_large_n_max0, 23_large_n_max1, 23_large_n_max2, 23_large_n_max3, 23_large_n_max4, 24_large_1g_max0, 24_large_1g_max1, 24_large_1g_max2, 24_large_1g_max3, 24_large_1g_max4, 25_large_mg_max0, 25_large_mg_max1, 25_large_mg_max2, 25_large_mg_max3, 25_large_mg_max4, 26_corner0, 26_corner1, 26_corner2, 26_corner3, 26_corner4, 26_corner5, 26_corner6, sample01, sample02, sample03, sample04, sample05 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_small_n_random0 | AC | 1 ms | 256 KB |
00_small_n_random1 | AC | 1 ms | 256 KB |
00_small_n_random2 | AC | 1 ms | 256 KB |
01_small_1g_random0 | AC | 1 ms | 256 KB |
01_small_1g_random1 | AC | 1 ms | 256 KB |
01_small_1g_random2 | AC | 1 ms | 256 KB |
02_small_mg_random0 | AC | 1 ms | 256 KB |
02_small_mg_random1 | AC | 1 ms | 256 KB |
02_small_mg_random2 | AC | 1 ms | 256 KB |
10_medium_n_random0 | AC | 1 ms | 256 KB |
10_medium_n_random1 | AC | 2 ms | 256 KB |
10_medium_n_random2 | AC | 2 ms | 256 KB |
11_medium_1g_random0 | AC | 2 ms | 256 KB |
11_medium_1g_random1 | AC | 2 ms | 256 KB |
11_medium_1g_random2 | AC | 2 ms | 256 KB |
12_medium_mg_random0 | AC | 2 ms | 256 KB |
12_medium_mg_random1 | AC | 2 ms | 256 KB |
12_medium_mg_random2 | AC | 2 ms | 256 KB |
20_large_n_random0 | AC | 97 ms | 4864 KB |
20_large_n_random1 | AC | 125 ms | 3712 KB |
20_large_n_random2 | AC | 80 ms | 2304 KB |
21_large_1g_random0 | AC | 66 ms | 4988 KB |
21_large_1g_random1 | AC | 21 ms | 1408 KB |
21_large_1g_random2 | AC | 61 ms | 4092 KB |
22_large_mg_random0 | AC | 50 ms | 2432 KB |
22_large_mg_random1 | AC | 76 ms | 3712 KB |
22_large_mg_random2 | AC | 89 ms | 5632 KB |
23_large_n_max0 | AC | 174 ms | 6912 KB |
23_large_n_max1 | AC | 174 ms | 6912 KB |
23_large_n_max2 | AC | 173 ms | 6912 KB |
23_large_n_max3 | AC | 173 ms | 6912 KB |
23_large_n_max4 | AC | 173 ms | 6912 KB |
24_large_1g_max0 | AC | 167 ms | 6780 KB |
24_large_1g_max1 | AC | 110 ms | 6012 KB |
24_large_1g_max2 | AC | 166 ms | 6780 KB |
24_large_1g_max3 | AC | 110 ms | 6012 KB |
24_large_1g_max4 | AC | 110 ms | 6012 KB |
25_large_mg_max0 | AC | 174 ms | 7168 KB |
25_large_mg_max1 | AC | 175 ms | 7168 KB |
25_large_mg_max2 | AC | 175 ms | 7168 KB |
25_large_mg_max3 | AC | 175 ms | 7296 KB |
25_large_mg_max4 | AC | 174 ms | 7168 KB |
26_corner0 | AC | 56 ms | 7680 KB |
26_corner1 | AC | 1 ms | 256 KB |
26_corner2 | AC | 104 ms | 6012 KB |
26_corner3 | AC | 43 ms | 1024 KB |
26_corner4 | AC | 137 ms | 4352 KB |
26_corner5 | AC | 131 ms | 4352 KB |
26_corner6 | AC | 131 ms | 4352 KB |
sample01 | AC | 1 ms | 256 KB |
sample02 | AC | 1 ms | 256 KB |
sample03 | AC | 1 ms | 256 KB |
sample04 | AC | 1 ms | 256 KB |
sample05 | AC | 1 ms | 256 KB |