// no matter how hard you work, someone else is working harder
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _i = (b); i <= _i; ++ i)
#define FORD(i, b, a) for (int i = (b), _i = (a); i >= _i; -- i)
#define REP(i, b) for (int i = 0, _i = (b); i < _i; ++ i)
#define FORE(i, a) for (auto& i : a)
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define cntbit __builtin_popcountll
#define len(x) (int)x.size()
#define bit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
template <typename A, typename B>
inline bool ckmax(A& a, const B& b) {
if (a < b) {
a = b;
return true;
} return false;
}
template <typename A, typename B>
inline bool ckmin(A& a, const B& b) {
if (a > b) {
a = b;
return true;
} return false;
}
inline void fileIO(const string& Task = "") {
ios::sync_with_stdio(false); cin.tie(NULL);
if (fopen((Task + ".inp").c_str(), "r")) {
freopen((Task + ".inp").c_str(), "r", stdin);
freopen((Task + ".out").c_str(), "w", stdout);
}
}
/* Author: Hoang Quoc Viet */
/** END OF TEMPLATE **/
int n, a[100005];
int lab[100005];
vector<int> comp[100005];
int find_set(int u) {
return lab[u] < 0? u : lab[u] = find_set(lab[u]);
}
bool unite(int u, int v) {
u = find_set(u);
v = find_set(v);
if (u ^ v) {
if (lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
comp[u].insert(comp[u].end(), all(comp[v]));
return true;
} return false;
}
int main() {
fileIO("main");
cin >> n;
FOR(i, 1, n) cin >> a[i];
memset(lab, -1, sizeof lab);
multiset<pair<int, int>> ms;
FOR(i, 1, n) {
comp[i].pb(i);
ms.insert(mp(a[i], i));
}
ll res = 0;
int numComp = n;
while (numComp > 1) {
vector<pair<int, int>> safeEdge;
FOR(i, 1, n) if (len(comp[i])) {
FORE(u, comp[i]) ms.erase(mp(a[u], u));
int mn = 1e9, tmp, cur;
FORE(u, comp[i]) {
int x = (*ms.begin()).F;
if (ckmin(mn, a[u] + x)) {
tmp = u;
cur = (*ms.begin()).S;
}
}
FORE(u, comp[i]) ms.insert(mp(a[u], u));
safeEdge.pb(mp(tmp, cur));
}
FORE(p, safeEdge) if (unite(p.F, p.S)) {
res += a[p.F] + a[p.S];
-- numComp;
}
}
cout << res;
return 0;
}
/*** VOI VOI VOI important things must be said three times :> ***/
Compilation message
Main.cpp: In function 'void fileIO(const string&)':
Main.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen((Task + ".inp").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen((Task + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:93:36: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
93 | safeEdge.pb(mp(tmp, cur));
| ^
Main.cpp:93:36: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2912 KB |
Output is correct |
| 2 |
Correct |
65 ms |
12476 KB |
Output is correct |
| 3 |
Execution timed out |
1022 ms |
13568 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3020 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3052 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2912 KB |
Output is correct |
| 2 |
Correct |
65 ms |
12476 KB |
Output is correct |
| 3 |
Execution timed out |
1022 ms |
13568 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
