Submission #3449165
Source Code Expand
/* ---------- STL Libraries ---------- */ // IO library #include <cstdio> #include <fstream> #include <iomanip> #include <ios> #include <iostream> // algorithm library #include <algorithm> #include <cmath> #include <numeric> #include <random> // container library #include <array> #include <bitset> #include <deque> #include <map> #include <queue> #include <set> #include <string> #include <tuple> #include <vector> /* ---------- Namespace ---------- */ using namespace std; /* ---------- Type Abbreviation ---------- */ template <typename T> using PQ = priority_queue<T>; template <typename T> using GPQ = priority_queue<T, vector<T>, greater<T>>; using ll = long long; #define fst first #define snd second #define mp make_pair #define mt make_tuple /* ---------- conversion ---------- */ #define INT(c) static_cast<int>(c) #define CHAR(n) static_cast<char>(n) #define LL(n) static_cast<ll>(n) #define DOUBLE(n) static_cast<double>(n) /* ---------- container ---------- */ #define ALL(v) (v).begin(), (v).end() #define SIZE(v) (LL((v).size())) #define FIND(v, k) (v).find(k) != (v).end() #define VFIND(v, k) find(ALL(v), k) != (v).end() #define gsort(b, e) sort(b, e, greater<decltype(*b)>()) /* ----------- debug ---------- */ template <class T> ostream& operator<<(ostream& os, vector<T> v) { os << "["; for (auto vv : v) os << vv << ","; return os << "]"; } template <class T> ostream& operator<<(ostream& os, set<T> v) { os << "["; for (auto vv : v) os << vv << ","; return os << "]"; } template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fst << "," << p.snd << ")"; } /* ---------- Constants ---------- */ // const ll MOD = 1e9 + 7; // const int INF = 1 << 25; const ll INF = 1LL << 50; // const double PI = acos(-1); // const double EPS = 1e-10; // mt19937 mert(LL(time(0))); /* ---------- Short Functions ---------- */ template <typename T> T sq(T a) { return a * a; } template <typename T> T gcd(T a, T b) { if (a > b) return gcd(b, a); return a == 0 ? b : gcd(b % a, a); } template <typename T, typename U> T mypow(T b, U n) { if (n == 0) return 1; if (n == 1) return b /* % MOD */; if (n % 2 == 0) { return mypow(b * b /* % MOD */, n / 2); } else { return mypow(b, n - 1) * b /* % MOD */; } } ll pcnt(ll b) { return __builtin_popcountll(b); } /* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */ 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); fill(num, num + V_NUM, 1); } // 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; // rank[x] >= rank[y]にする if (rank[x] < rank[y]) swap(x, y); // rankの大きい方、つまりxにyをくっつける num[x] += num[y]; par[y] = x; if (rank[x] == rank[y]) ++rank[x]; } // xとyが同じグループに属するか判定 bool same(int x, int y) { return find(x) == find(y); } // xが属するグループの要素数を返す int size(int v) { return num[v]; } const int INF = 1 << 25; int V_NUM; int par[MAX_V], rank[MAX_V], num[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); for (int i = 0; i < M; ++i) { ++sz[uf.find(x[i])]; } vector<int> child[N]; for (int i = 0; i < N; ++i) { child[uf.find(i)].push_back(i); } for (int i = 0; i < N; ++i) { if (i == uf.find(i) && uf.size(i) == sz[i] + 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 | 4727 Byte |
Status | AC |
Exec Time | 181 ms |
Memory | 8064 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 | 1 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 | 384 KB |
11_medium_1g_random2 | AC | 1 ms | 256 KB |
12_medium_mg_random0 | AC | 1 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 | 98 ms | 5120 KB |
20_large_n_random1 | AC | 125 ms | 3840 KB |
20_large_n_random2 | AC | 80 ms | 2304 KB |
21_large_1g_random0 | AC | 66 ms | 5372 KB |
21_large_1g_random1 | AC | 22 ms | 1536 KB |
21_large_1g_random2 | AC | 61 ms | 4348 KB |
22_large_mg_random0 | AC | 50 ms | 2560 KB |
22_large_mg_random1 | AC | 76 ms | 3968 KB |
22_large_mg_random2 | AC | 89 ms | 6016 KB |
23_large_n_max0 | AC | 175 ms | 7296 KB |
23_large_n_max1 | AC | 173 ms | 7296 KB |
23_large_n_max2 | AC | 174 ms | 7296 KB |
23_large_n_max3 | AC | 172 ms | 7296 KB |
23_large_n_max4 | AC | 177 ms | 7296 KB |
24_large_1g_max0 | AC | 168 ms | 7164 KB |
24_large_1g_max1 | AC | 113 ms | 6396 KB |
24_large_1g_max2 | AC | 167 ms | 7164 KB |
24_large_1g_max3 | AC | 110 ms | 6396 KB |
24_large_1g_max4 | AC | 111 ms | 6396 KB |
25_large_mg_max0 | AC | 181 ms | 7552 KB |
25_large_mg_max1 | AC | 174 ms | 7552 KB |
25_large_mg_max2 | AC | 175 ms | 7552 KB |
25_large_mg_max3 | AC | 177 ms | 7552 KB |
25_large_mg_max4 | AC | 176 ms | 7552 KB |
26_corner0 | AC | 56 ms | 8064 KB |
26_corner1 | AC | 1 ms | 256 KB |
26_corner2 | AC | 104 ms | 6396 KB |
26_corner3 | AC | 43 ms | 1024 KB |
26_corner4 | AC | 131 ms | 4480 KB |
26_corner5 | AC | 131 ms | 4480 KB |
26_corner6 | AC | 131 ms | 4480 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 |