#include <stdio.h>
#define NN 1000001
#define MM 2000002
long long max(long long i, long long j) {return i > j ? i : j;}
int n, ww[MM], to[MM], lnk[MM], head[NN], col[NN];
void link(int u, int v, int w) {
static int ii = 0;
int i = ++ii;
to[i] = v;
ww[i] = w;
lnk[i] = head[u];
head[u] = i;
}
int cycle_head, cycle_tail;
int cyc[NN], co, par[NN], incyc[NN];
long long tentacle[NN], tentacle2[NN], aa[NN], here;
int dfs(int u, int pe) {
col[u] = 1;
for (int j = head[u]; j; j = lnk[j]) if ((j + 1) / 2 - (pe + 1) / 2) {
int v = to[j];
if (col[v]) {
cycle_head = u;
cycle_tail = v;
co = 0;
int cur = u;
for (; cur != v && cur != -1; cur = par[cur])
incyc[cyc[co++] = cur] = 1;
incyc[cyc[co++] = v] = 1;
return 1;
}
par[v] = u;
if (dfs(v, j))
return 1;
}
return 0;
}
void dfs2(int u, int p) {
col[u] = 1;
for (int j = head[u]; j; j = lnk[j]) {
int v = to[j];
if (v == p || incyc[v]) continue;
dfs2(v, u);
if (tentacle2[v] + ww[j] >= tentacle[u])
tentacle2[u] = tentacle[u], tentacle[u] = tentacle2[v] + ww[j];
else if (tentacle2[v] + ww[j] >= tentacle2[u])
tentacle2[u] = tentacle2[v] + ww[j];
if (tentacle[v] + ww[j] >= tentacle[u])
tentacle2[u] = tentacle[u], tentacle[u] = tentacle[v] + ww[j];
else if (tentacle[v] + ww[j] >= tentacle2[u])
tentacle2[u] = tentacle[v] + ww[j];
}
here = max(tentacle[u], tentacle2[u]);
}
long long answer = 0;
int main() {
scanf("%d", &n);
for (int i = 1, j, k; i <= n; ++i)
scanf("%d%d", &j, &k), link(i, j, k), link(j, i, k);
for (int ii = 1; ii <= n; ++ii) {
if (col[ii]) continue;
par[ii] = -1;
dfs(ii, -1);
long long op0 = -1e18, op1 = -1e18;
here = 0;
long long cycle_w = 0;
for (int i = 0; i < co; ++i) {
for (int j = head[cyc[i]]; j; j = lnk[j])
if (incyc[to[j]]) cycle_w += ww[j];
dfs2(cyc[i], -1);
}
cycle_w /= 2;
if (co == 2) {
for (int j = head[cycle_head]; j; j = lnk[j])
if (cycle_tail == to[j])
here = max(here, ww[j]+ tentacle[cycle_tail] + tentacle[cycle_head]);
answer += here;
continue;
}
for (int i = 0; i < co; ++i) {
here = max(here, tentacle[cyc[i]] + max(aa[i] + op0, -aa[i] + op1));
op0 = max(tentacle[cyc[i]] - aa[i], op0);
op1 = max(tentacle[cyc[i]] + cycle_w + aa[i], op1);
if (i + 1 < co)
for (int j = head[cyc[i]]; j; j = lnk[j])
if (to[j] == cyc[i + 1]) {
aa[i + 1] = aa[i] + ww[j];
break;
}
}
answer += here;
}
printf("%lld\n", answer);
}
Compilation message
islands.c: In function 'main':
islands.c:72:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
islands.c:74:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d%d", &j, &k), link(i, j, k), link(j, i, k);
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 8 |
Correct |
0 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
4444 KB |
Output isn't correct |
| 11 |
Correct |
1 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
10 ms |
5212 KB |
Output is correct |
| 3 |
Correct |
5 ms |
3420 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
4956 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
15 ms |
9364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
13208 KB |
Output is correct |
| 2 |
Correct |
36 ms |
16208 KB |
Output is correct |
| 3 |
Correct |
49 ms |
25360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
22356 KB |
Output is correct |
| 2 |
Correct |
115 ms |
42620 KB |
Output is correct |
| 3 |
Correct |
113 ms |
44700 KB |
Output is correct |
| 4 |
Correct |
121 ms |
64168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
137 ms |
31684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
131072 KB |
Output is correct |
| 2 |
Incorrect |
211 ms |
90196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
