#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000002;
int n, A, par[MAXN], ed, bg, V, P;
long long int mx_dist, ans, c[MAXN], dist;
vector<int> graph[MAXN], cost[MAXN], tree, cycle;
bool mark[MAXN];
void dfs1()
{
// printf("v = %d p = %d\n", v, p);
tree.push_back(V);
mark[V] = true;
par[V] = P;
bool aux = true;
for(int i = 0; i < graph[V].size(); i++)
{
int cur = graph[V][i];
if(cur == P && aux){ aux = false; continue; }
if(mark[cur])
{
if(!bg && !ed) ed = V, bg = cur, par[cur] = V, c[cur] = cost[V][i];
continue;
}
int auxV = V, auxP = P;
c[cur] = cost[V][i];
P = V, V = cur;
dfs1();
V = auxV, P = auxP;
}
}
void dfs2()
{
mark[V] = true;
tree.push_back(V);
if(dist > mx_dist) mx_dist = dist, A = V;
for(int i = 0; i < graph[V].size(); i++)
{
int cur = graph[V][i];
if(mark[cur]) continue;
dist += cost[V][i];
int aux = V;
V = cur;
dfs2();
V = aux;
dist -= cost[V][i];
}
}
int main ()
{
scanf("%d", &n);
for(int i = 1, j, l; i <= n; i++)
{
scanf("%d %d", &j, &l);
graph[i].push_back(j), cost[i].push_back(l);
graph[j].push_back(i), cost[j].push_back(l);
}
for(int i = 1; i <= n; i++)
{
if(mark[i]) continue;
bg = ed = 0;
tree.clear(); cycle.clear();
V = P = i;
dfs1();
int cur = ed;
while(cur != bg) cycle.push_back(cur), cur = par[cur];
cycle.push_back(cur);
for(int j = 0; j < tree.size(); j++) mark[tree[j]] = false;
for(int j = 0; j < cycle.size(); j++) mark[cycle[j]] = true;
long long int SCT = 0, SC = 0;
long long int max_DI_SCI[2] = {0, 0}, max_DJ_SCJ[2] = {0, 0}, ANS = 0;
for(int j = 0; j < cycle.size(); j++) SCT += c[cycle[j]];
for(int j = 0; j < cycle.size(); j++)
{
int v = A = cycle[j];
mark[v] = false, mx_dist = 0;
tree.clear();
V = v;
dfs2();
ANS = max(ANS, max_DI_SCI[0] + mx_dist + SC);
ANS = max(ANS, max_DI_SCI[1] + mx_dist - SC);
max_DI_SCI[0] = max(max_DI_SCI[0], mx_dist - SC);
max_DI_SCI[1] = max(max_DI_SCI[1], mx_dist + SC + SCT);
SC += c[v];
for(int k = 0; k < tree.size(); k++) mark[tree[k]] = false;
tree.clear();
V = A;
dfs2();
ANS = max(ANS, mx_dist);
}
ans += ANS;
}
printf("%lld\n", ans);
}
Compilation message
islands.cpp: In function 'void dfs1()':
islands.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < graph[V].size(); i++)
~~^~~~~~~~~~~~~~~~~
islands.cpp: In function 'void dfs2()':
islands.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < graph[V].size(); i++)
~~^~~~~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < tree.size(); j++) mark[tree[j]] = false;
~~^~~~~~~~~~~~~
islands.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < cycle.size(); j++) mark[cycle[j]] = true;
~~^~~~~~~~~~~~~~
islands.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < cycle.size(); j++) SCT += c[cycle[j]];
~~^~~~~~~~~~~~~~
islands.cpp:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < cycle.size(); j++)
~~^~~~~~~~~~~~~~
islands.cpp:105:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = 0; k < tree.size(); k++) mark[tree[k]] = false;
~~^~~~~~~~~~~~~
islands.cpp:84:41: warning: unused variable 'max_DJ_SCJ' [-Wunused-variable]
long long int max_DI_SCI[2] = {0, 0}, max_DJ_SCJ[2] = {0, 0}, ANS = 0;
^~~~~~~~~~
islands.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
islands.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &j, &l);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
47224 KB |
Output is correct |
| 2 |
Correct |
29 ms |
47352 KB |
Output is correct |
| 3 |
Correct |
29 ms |
47352 KB |
Output is correct |
| 4 |
Correct |
30 ms |
47360 KB |
Output is correct |
| 5 |
Correct |
29 ms |
47360 KB |
Output is correct |
| 6 |
Correct |
29 ms |
47360 KB |
Output is correct |
| 7 |
Correct |
28 ms |
47360 KB |
Output is correct |
| 8 |
Correct |
28 ms |
47360 KB |
Output is correct |
| 9 |
Correct |
29 ms |
47360 KB |
Output is correct |
| 10 |
Correct |
28 ms |
47360 KB |
Output is correct |
| 11 |
Correct |
29 ms |
47360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
47360 KB |
Output is correct |
| 2 |
Correct |
30 ms |
47464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
47488 KB |
Output is correct |
| 2 |
Correct |
32 ms |
47744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
48672 KB |
Output is correct |
| 2 |
Correct |
61 ms |
51320 KB |
Output is correct |
| 3 |
Correct |
47 ms |
49144 KB |
Output is correct |
| 4 |
Correct |
36 ms |
48248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
52728 KB |
Output is correct |
| 2 |
Correct |
96 ms |
56316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
65136 KB |
Output is correct |
| 2 |
Correct |
165 ms |
70516 KB |
Output is correct |
| 3 |
Correct |
195 ms |
78060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
262 ms |
78840 KB |
Output is correct |
| 2 |
Correct |
327 ms |
101468 KB |
Output is correct |
| 3 |
Correct |
362 ms |
112104 KB |
Output is correct |
| 4 |
Correct |
442 ms |
125784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
473 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
559 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
