#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll A[1000006];
int heapSize=0;
int leftNode(int i)
{
return i*2;
}
int rightNode(int i)
{
return i*2+1;
}
int parent(int i)
{
return i/2;
}
void maxHeapify(int i)
{
int L=leftNode(i);
int R=rightNode(i);
int best;
if(L<=heapSize && A[L]>A[i])
best=L;
else
best=i;
if(R<=heapSize && A[R]>A[best])
best=R;
if(best!=i){
swap(A[i],A[best]);
maxHeapify(best);
}
}
void increaseKey(int i,ll key)
{
if(A[i]>key) return;
A[i]=key;
while(i>1 && A[i]>A[parent(i)]){
swap(A[i],A[parent(i)]);
i=parent(i);
}
}
void heapInsert(ll x)
{
A[++heapSize]=-LLONG_MAX;
increaseKey(heapSize,x);
}
ll extractMax()
{
ll maximum=A[1];
A[1]=A[heapSize--];
maxHeapify(1);
return maximum;
}
ll viewMax()
{
return A[1];
}
struct edge{
int from,to;
int w;
int id;
};
int n;
int color[1000006];
int p[1000006];
int id[1000006];
int weight[1000006];
ll sumCycle;
vector<edge> eCycle;
vector<int> cycle;
vector<edge> adjList[1000006];
void dfsVisit(int u)
{
color[u]=1;
for(edge e: adjList[u]){
int v=e.to;
if(id[u]==e.id) continue;
if(color[v]==0){
id[v]=e.id;
p[v]=u;
weight[v]=e.w;
dfsVisit(v);
}
else if(color[v]==1){ //Cycle
edge x=e;
swap(x.from,x.to);
eCycle.push_back(x);
swap(x.from,x.to);
while(x.from!=v){
x.to=p[x.from];
x.id=id[x.from];
x.w=weight[x.from];
eCycle.push_back(x);
x.from=x.to;
}
}
}
color[u]=-1;
}
queue<int> Q;
ll d[1000006];
ll longest[1000006];
ll SL[1000006];
int c=1;
ll diameter(int root)
{
d[root]=0;
color[root]=c;
Q.push(root);
ll maximum=0;
int node=root;
while(Q.size()){
int u=Q.front();
Q.pop();
for(edge e: adjList[u]){
int v=e.to;
if(v==0) continue;
if(color[v]!=c){
color[v]=c;
d[v]=d[u]+(ll)e.w;
if(d[v]>maximum){
maximum=d[v];
node=v;
}
Q.push(v);
}
}
}
longest[root]=maximum;
maximum=0;
d[node]=0;
Q.push(node);
c++;
color[node]=c;
while(Q.size()){
int u=Q.front();
Q.pop();
for(edge e: adjList[u]){
int v=e.to;
if(v==0) continue;
if(color[v]!=c){
color[v]=c;
d[v]=d[u]+(ll)e.w;
if(d[v]>maximum){
maximum=d[v];
node=v;
}
Q.push(v);
}
}
}
return maximum;
}
ll maxPath(int root)
{
ll maximum=0;
sumCycle=0;
int i=0;
for(edge e: eCycle){
cycle.push_back(e.from);
sumCycle+=(ll)e.w;
SL[e.to]=SL[e.from]+(ll)e.w;
}
eCycle.clear();
SL[cycle[0]]=0;
int C=cycle.size();
++c;
for(int i=0;i<cycle.size();i++){
int u=cycle[i];
int a=cycle[(i-1+C)%C];
int b=cycle[(i+1)%C];
for(int j=0;j<adjList[u].size();j++){
if(adjList[u][j].to==a || adjList[u][j].to==b) adjList[u][j].to=0;
}
maximum=max(maximum,diameter(u)); //Gets the diameter of the tree rooted at u
}
//The maximum is given by selecting all pairs i,j of nodes in the cycle
//The sum of the longest path in tree rooted at i and tree rooted at j
//And the maxPath in the cycle between i and j
//ans= max (max _i<j_ {(longest[i]-SL[i])+(longest[j]+SL[j])},
// sumCycle max _i<j_ {(longest[i]+SL[i])+(longest[j]-SL[j])} )
for(int j=1;j<cycle.size();j++){
ll a=longest[ cycle[j-1] ]-SL[ cycle[j-1] ]; //Inserts term i
heapInsert(a);
a=viewMax(); //Gets the maximum for all the pasts terms i
ll b=longest[ cycle[j] ]+SL[ cycle[j] ]; //Term j
maximum=max(maximum,a+b);
}
while(heapSize) extractMax();
for(int j=1;j<cycle.size();j++){
ll a=longest[ cycle[j-1] ]+SL[ cycle[j-1] ]; //Inserts term i
heapInsert(a);
a=viewMax(); //Gets the maximum for all the past terms i
ll b=longest[ cycle[j] ]-SL[ cycle[j] ]; //Term j
maximum=max(maximum,sumCycle+a+b);
}
while(heapSize) extractMax();
return maximum;
}
ll total=0;
void dfs()
{
for(int i=1;i<=n;i++){
if(color[i]==0){
dfsVisit(i);
total+=maxPath(i);
cycle.clear();
}
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int a;
int b;
cin>>a>>b;
edge e;
e.from=i;
e.to=a;
e.w=b;
e.id=i;
adjList[e.from].push_back(e);
swap(e.from,e.to);
adjList[e.from].push_back(e);
}
dfs();
cout<<total<<'\n';
return 0;
}
Compilation message
islands.cpp: In function 'll maxPath(int)':
islands.cpp:169:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cycle.size();i++){
~^~~~~~~~~~~~~
islands.cpp:173:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<adjList[u].size();j++){
~^~~~~~~~~~~~~~~~~~
islands.cpp:183:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=1;j<cycle.size();j++){
~^~~~~~~~~~~~~
islands.cpp:191:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=1;j<cycle.size();j++){
~^~~~~~~~~~~~~
islands.cpp:159:9: warning: unused variable 'i' [-Wunused-variable]
int i=0;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23932 KB |
Output is correct |
| 3 |
Correct |
24 ms |
23980 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 7 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 8 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 9 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 10 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 11 |
Correct |
23 ms |
23928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
24 ms |
24092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
26 ms |
24440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
25592 KB |
Output is correct |
| 2 |
Correct |
52 ms |
28916 KB |
Output is correct |
| 3 |
Correct |
38 ms |
25976 KB |
Output is correct |
| 4 |
Correct |
31 ms |
24824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
30644 KB |
Output is correct |
| 2 |
Correct |
85 ms |
34872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
44116 KB |
Output is correct |
| 2 |
Correct |
183 ms |
51044 KB |
Output is correct |
| 3 |
Correct |
221 ms |
63904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
256 ms |
61472 KB |
Output is correct |
| 2 |
Correct |
355 ms |
91720 KB |
Output is correct |
| 3 |
Correct |
456 ms |
103000 KB |
Output is correct |
| 4 |
Correct |
508 ms |
130068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
439 ms |
98592 KB |
Output is correct |
| 2 |
Runtime error |
682 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
474 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
