#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];
stack<edge> S;
ll sumCycle;
vector<edge> eCycle;
vector<int> cycle;
vector<edge> adjList[1000006];
void dfsVisit(int u,int id)
{
color[u]=1;
for(edge e: adjList[u]){
int v=e.to;
if(id==e.id) continue;
if(color[v]==0){
swap(e.from,e.to);
S.push(e);
swap(e.from,e.to);
dfsVisit(v,e.id);
}
else if(color[v]==1){ //Cycle
edge x=e;
swap(x.from,x.to);
eCycle.push_back(x);
swap(x.from,x.to);
x=S.top();
S.pop();
while(x.to!=v){
eCycle.push_back(x);
x=S.top();
S.pop();
}
eCycle.push_back(x);
}
}
if(S.size()) S.pop();
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,0);
//total+=maxPath(i);
total+=1;
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 |
Incorrect |
24 ms |
23800 KB |
Output isn't correct |
| 2 |
Incorrect |
24 ms |
23800 KB |
Output isn't correct |
| 3 |
Incorrect |
23 ms |
23928 KB |
Output isn't correct |
| 4 |
Incorrect |
24 ms |
23800 KB |
Output isn't correct |
| 5 |
Incorrect |
24 ms |
23800 KB |
Output isn't correct |
| 6 |
Incorrect |
24 ms |
23800 KB |
Output isn't correct |
| 7 |
Incorrect |
24 ms |
23800 KB |
Output isn't correct |
| 8 |
Incorrect |
24 ms |
23800 KB |
Output isn't correct |
| 9 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 10 |
Incorrect |
24 ms |
23932 KB |
Output isn't correct |
| 11 |
Incorrect |
23 ms |
23928 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
24056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
24056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
25336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
30036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
40160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
210 ms |
56404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
392 ms |
90376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
477 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
