| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 351274 |
2021-01-19T19:52:45 Z |
parsabahrami |
Toll (APIO13_toll) |
C++17 |
|
2500 ms |
17900 KB |
// When will those clouds all disappear?
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 3e5 + 50, MOD = 1e9 + 7;
int par[N], val[N], H[N], M[N], id[N], rt[N], U[N], V[N], W[N], M2[N], n, m, k;
vector<int> adj[N], vec, roots; ll ret, tot, P[N], S[N];
int Find(int v) {
return !rt[v] ? v : rt[v] = Find(rt[v]);
}
int Union(int u, int v) {
u = Find(u), v = Find(v);
return u == v ? 0 : bool(rt[u] = v);
}
inline void init() {
fill(rt, rt + N, 0);
}
void DFS(int v, int p = -1) {
S[v] = P[v];
for (int i : adj[v]) {
int u = U[i] ^ V[i] ^ v;
if (u != p) {
par[u] = i;
H[u] = H[v] + 1;
DFS(u, v);
S[v] += S[u];
}
}
}
int main() {
fill(val, val + N, MOD);
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &U[i], &V[i], &W[i]);
id[i] = i;
}
sort(id + 1, id + m + 1, [&](int i, int j) {
return W[i] < W[j];
});
for (int i = 1; i <= k; i++) {
scanf("%d%d", &U[i + m], &V[i + m]);
}
for (int i = 1; i <= m; i++) {
M[i] = Union(U[id[i]], V[id[i]]);
}
init();
for (int i = m + 1; i <= m + k; i++) {
Union(U[i], V[i]);
}
for (int i = 1; i <= m + k; i++) {
M2[i] = Union(U[id[i]], V[id[i]]);
}
init();
for (int i = 1; i <= m; i++) {
if (M2[i]) Union(U[id[i]], V[id[i]]);
if (!M2[i] && M[i]) vec.push_back(i);
}
for (int i = 1; i <= n; i++) {
scanf("%lld", &P[i]);
}
for (int i = 1; i <= n; i++) {
if (!rt[i]) roots.push_back(i);
else P[Find(i)] += P[i];
}
for (int i = 1; i <= m + k; i++) U[i] = Find(U[i]), V[i] = Find(V[i]);
int R = Find(1);
init();
for (int msk = 1; msk < 1 << k; msk++) {
for (int v : roots) adj[v] = {}, rt[v] = 0;
int f = 1;
for (int i = m + 1; i <= m + k; i++) {
int j = i - m - 1; val[i] = 2e9;
if (msk & (1 << j)) {
f &= Union(U[i], V[i]);
adj[U[i]].push_back(i);
adj[V[i]].push_back(i);
}
}
if (!f) break;
for (int i : vec) {
if (Union(U[id[i]], V[id[i]])) {
adj[U[id[i]]].push_back(id[i]);
adj[V[id[i]]].push_back(id[i]);
}
}
DFS(R); tot = 0;
for (int i : vec) {
int u = U[id[i]], v = V[id[i]], w = W[id[i]];
while (u != v) {
if (H[u] < H[v]) {
if (w < val[par[v]]) val[par[v]] = w;
v = U[par[v]] ^ V[par[v]] ^ v;
}
else {
if (w < val[par[u]]) val[par[u]] = w;
u = U[par[u]] ^ V[par[u]] ^ u;
}
}
}
for (int v : roots) {
if (par[v] > m) tot += S[v] * val[par[v]];
}
ret = max(ret, tot);
}
printf("%lld\n", ret);
return 0;
}
Compilation message
toll.cpp:3: warning: ignoring #pragma comment [-Wunknown-pragmas]
3 | #pragma comment(linker, "/stack:200000000")
|
toll.cpp: In function 'int Union(int, int)':
toll.cpp:25:39: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
25 | return u == v ? 0 : bool(rt[u] = v);
| ^
toll.cpp: In function 'int main()':
toll.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
47 | scanf("%d%d%d", &n, &m, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
49 | scanf("%d%d%d", &U[i], &V[i], &W[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
56 | scanf("%d%d", &U[i + m], &V[i + m]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
74 | scanf("%lld", &P[i]);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9836 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9836 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9836 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9836 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9836 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9836 KB |
Output is correct |
| 5 |
Correct |
9 ms |
9964 KB |
Output is correct |
| 6 |
Correct |
9 ms |
9964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9836 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9836 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9836 KB |
Output is correct |
| 5 |
Correct |
9 ms |
9964 KB |
Output is correct |
| 6 |
Correct |
9 ms |
9964 KB |
Output is correct |
| 7 |
Correct |
261 ms |
17804 KB |
Output is correct |
| 8 |
Correct |
274 ms |
17852 KB |
Output is correct |
| 9 |
Correct |
264 ms |
17772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9836 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9836 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9836 KB |
Output is correct |
| 5 |
Correct |
9 ms |
9964 KB |
Output is correct |
| 6 |
Correct |
9 ms |
9964 KB |
Output is correct |
| 7 |
Correct |
261 ms |
17804 KB |
Output is correct |
| 8 |
Correct |
274 ms |
17852 KB |
Output is correct |
| 9 |
Correct |
264 ms |
17772 KB |
Output is correct |
| 10 |
Correct |
2078 ms |
17900 KB |
Output is correct |
| 11 |
Execution timed out |
2536 ms |
17772 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
