#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000002;
int n, A, par[MAXN], ed, bg;
long long int dist[MAXN], mx_dist, ans, c[MAXN];
vector<int> graph[MAXN], cost[MAXN], tree, cycle;
bool mark[MAXN];
void dfs1(int v, int p)
{
// 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;
}
c[cur] = cost[v][i];
dfs1(cur, v);
}
return;
}
void dfs2(int v)
{
mark[v] = true;
tree.push_back(v);
if(dist[v] > mx_dist) mx_dist = dist[v], A = v;
for(int i = 0; i < graph[v].size(); i++)
{
int cur = graph[v][i];
if(mark[cur]) continue;
dist[cur] = dist[v] + cost[v][i];
dfs2(cur);
}
return;
}
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();
dfs1(i, i);
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[5], ANS = 0;
max_DI_SCI[0] = 0;
max_DI_SCI[1] = 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 = dist[v] = 0;
tree.clear();
dfs2(v);
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;
dist[A] = 0; tree.clear();
dfs2(A);
ANS = max(ANS, mx_dist);
}
ans += ANS;
}
printf("%lld\n", ans);
}
Compilation message
islands.cpp: In function 'void dfs1(int, int)':
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(int)':
islands.cpp:42: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:76: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:77: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:84: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:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < cycle.size(); j++)
~~^~~~~~~~~~~~~~
islands.cpp:102: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:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
islands.cpp:59: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 |
30 ms |
47360 KB |
Output is correct |
| 2 |
Correct |
29 ms |
47488 KB |
Output is correct |
| 3 |
Correct |
37 ms |
47352 KB |
Output is correct |
| 4 |
Correct |
30 ms |
47360 KB |
Output is correct |
| 5 |
Correct |
35 ms |
47360 KB |
Output is correct |
| 6 |
Correct |
32 ms |
47352 KB |
Output is correct |
| 7 |
Correct |
29 ms |
47360 KB |
Output is correct |
| 8 |
Correct |
30 ms |
47360 KB |
Output is correct |
| 9 |
Correct |
32 ms |
47352 KB |
Output is correct |
| 10 |
Correct |
35 ms |
47352 KB |
Output is correct |
| 11 |
Correct |
29 ms |
47360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
47488 KB |
Output is correct |
| 2 |
Correct |
37 ms |
47488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
47488 KB |
Output is correct |
| 2 |
Correct |
33 ms |
47872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
48888 KB |
Output is correct |
| 2 |
Correct |
55 ms |
51556 KB |
Output is correct |
| 3 |
Correct |
46 ms |
49576 KB |
Output is correct |
| 4 |
Correct |
37 ms |
48376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
53496 KB |
Output is correct |
| 2 |
Correct |
88 ms |
57976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
155 ms |
68716 KB |
Output is correct |
| 2 |
Correct |
165 ms |
73204 KB |
Output is correct |
| 3 |
Correct |
218 ms |
80616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
263 ms |
87032 KB |
Output is correct |
| 2 |
Correct |
364 ms |
108056 KB |
Output is correct |
| 3 |
Correct |
393 ms |
118248 KB |
Output is correct |
| 4 |
Correct |
492 ms |
131072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
464 ms |
131076 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 |
564 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
