#pragma comment(linker, "/STACK: 2000000")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
#define f first
#define s second
int N;
ll ans;
int C;
int cycle[1000001],adjDis[1000001];
ll deepest[1000001];
int bad,bad2;
ll maxCur;
map<pair<int,int>,int>mp;
ll pref[1000001],suff[1000001];
pair<pair<int,int>,int> edges[2000005];
int L[1000001],R[1000001];
bool vis[1000001];
int cur;
void findCycle(int node, int par){
//cout<<"findCycle: "<<node<<endl;
vis[node]=1;
for (int i=L[node];i<=R[node];i++){
if (C==0 && vis[edges[i].f.s]==0 && edges[i].f.s!=par){ //found cycle
C=0;
//cout<<"found cycle"<<endl;
cur=node;
while (cur!=edges[i].f.s){
cycle[C]=cur;
adjDis[C]=deepest[cur]; //fromDis
C++;
cur=pref[cur]; //from
}
cycle[C]=edges[i].f.s;
adjDis[C]=edges[i].s;
C++;
}
else if (vis[edges[i].f.s]==0){
pref[edges[i].f.s]=node; //from
deepest[edges[i].f.s]=edges[i].s; //fromDis
findCycle(edges[i].f.s,node);
}
}
}
ll maxDis,maxNode;
queue<pair<pair<int,int>,ll>>q;
void findFarthest(int node0, int par0, ll dis0){
maxDis=-1; maxNode=-1;
q.push({{node0,par0},dis0});
while (!q.empty()){
q.pop();
int node=q.front().f.f;
int par=q.front().f.s;
ll dis=q.front().s;
q.pop();
if (dis>maxDis){
maxDis=dis;
maxNode=node;
}
for (int i=L[node];i<=R[node];i++){
if (edges[i].f.s!=par && edges[i].f.s!=bad && edges[i].f.s!=bad2)
q.push({{edges[i].f.s,node},dis+edges[i].s});
}
}
}
ll findDiameter(int node){
findFarthest(node,node,0);
int newNode=maxNode;
findFarthest(newNode,newNode,0);
return maxDis;
}
int main()
{
scanf("%d",&N);
for (int i=1;i<=N;i++){
L[i]=INF; R[i]=-INF;
int Y,L;
scanf("%d%d",&Y,&L);
int x=i,y=Y;
if (x>y) swap(x,y);
mp[{x,y}]=max(mp[{x,y}],L);
}
int E=0;
for (auto it:mp){
//cout<<"edge: "<<it.first.first<<' '<<it.first.second<<endl;
edges[E++]={{it.f.f,it.f.s},it.s};
edges[E++]={{it.f.s,it.f.f},it.s};
}
mp.clear();
sort(edges,edges+E);
for (int i=0;i<E;i++){
L[edges[i].f.f]=min(L[edges[i].f.f],i);
R[edges[i].f.f]=max(R[edges[i].f.f],i);
}
for (int i=1;i<=N;i++)
if (vis[i]==0){
//cout<<"Component: "<<i<<endl;
C=0;
findCycle(i,i);
/*
cout<<"Cycle: ";
for (int i=0;i<C;i++)
cout<<cycle[i]<<' '<<adjDis[i]<<endl;;
cout<<endl;
*/
if (C==0){
//cout<<"multiEdge: "<<findDiameter(i)<<endl;
ans+=findDiameter(i);
continue;
}
maxCur=0;
for (int i=0;i<C;i++){
pref[i]=0;
suff[i]=0;
int inFront=cycle[(i+1)%C];
int inBack=cycle[(i-1+C)%C];
//adjDis[i]=mp[{min(cycle[i],inFront),max(cycle[i],inFront)}];
bad=inFront;
bad2=inBack;
maxCur=max(maxCur,findDiameter(cycle[i]));
findFarthest(cycle[i],cycle[i],0);
deepest[i]=maxDis;
}
ll temp=0,temp2=0;
for (int i=0;i<C;i++){
if (i>0){
pref[i]=temp+adjDis[i-1];
temp=pref[i];
pref[i]=max(temp2,pref[i]+deepest[i]);
temp2=pref[i];
}
else{
pref[i]=deepest[i];
temp2=pref[i];
}
}
/*
cout<<"deepest: "<<' ';
for (int x:deepest)
cout<<x<<' ';
cout<<endl;
cout<<"adjDis: "<<' ';
for (int x:adjDis)
cout<<x<<' ';
cout<<endl;
cout<<"pref: ";
for (int i=0;i<C;i++)
cout<<pref[i]<<' ';
cout<<endl;
*/
temp=0; temp2=0;
for (int i=C-1;i>=0;i--){
if (i+1<C){
suff[i]=temp+adjDis[i];
temp=suff[i];
suff[i]=max(temp2,suff[i]+deepest[i]);
temp2=suff[i];
}
else{
suff[i]=deepest[i];
temp2=suff[i];
}
}
for (int i=0;i+1<C;i++){
//cout<<i<<": "<<adjDis.back()<<' '<<pref2[i]<<' '<<suff2[i+1]<<endl;
maxCur=max(maxCur,adjDis[C-1]+pref[i]+suff[i+1]);
}
ll sweep=0;
for (int i=0;i<C;i++){
maxCur=max(maxCur,sweep+deepest[i]);
sweep=max(sweep,(ll)deepest[i]);
sweep+=adjDis[i];
}
ans+=maxCur;
//cout<<"maxCur: "<<maxCur<<endl;
}
printf("%lld\n",ans);
}
Compilation message
islands.cpp:1:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/STACK: 2000000")
islands.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("O3")
islands.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
islands.cpp: In function 'int main()':
islands.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
~~~~~^~~~~~~~~
islands.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&Y,&L);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
16448 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
22 ms |
16384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
22 ms |
16384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
22 ms |
16384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
22 ms |
16384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
21 ms |
16384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
21 ms |
16384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
22 ms |
16384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
22 ms |
16384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
21 ms |
16512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
21 ms |
16512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
16512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
16640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
19328 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
25848 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
54596 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
322 ms |
92572 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1096 ms |
131072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
959 ms |
131072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
