#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
ll N;
ll L[1000001];
vector<pair<ll,ll>>adj[1000001];
bool vis[1000001];
ll ans;
ll from[1000001];
vector<ll>cycle,adjDis,deepest;
ll bad,bad2;
ll maxCur;
void findCycle(ll node, ll par){
//cout<<"findCycle: "<<node<<endl;
vis[node]=true;
for (auto p:adj[node]){
if (cycle.size()==0 && vis[p.first] && p.first!=par){ //found cycle
//cout<<"found cycle"<<endl;
ll cur=node;
while (cur!=p.first){
cycle.push_back(cur);
cur=from[cur];
}
cycle.push_back(p.first);
}
else if (!vis[p.first]){
from[p.first]=node;
findCycle(p.first,node);
}
}
}
ll maxDis,maxNode;
void findFarthest(ll node, ll par, ll dis){
if (dis>maxDis){
maxDis=dis;
maxNode=node;
}
for (auto p:adj[node]){
if (p.first!=par && p.first!=bad && p.first!=bad2)
findFarthest(p.first,node,dis+p.second);
}
}
ll findDiameter(ll node){
maxDis=-1; maxNode=-1;
findFarthest(node,node,0);
ll newNode=maxNode;
maxDis=-1; maxNode=-1;
findFarthest(newNode,newNode,0);
return maxDis;
}
ll getDeep(ll node, ll par, ll dis){
ll mx=dis;
for (auto p:adj[node]){
if (p.first!=par && p.first!=bad && p.first!=bad2)
mx=max(mx,getDeep(p.first,node,dis+p.second));
}
return mx;
}
map<pair<ll,ll>,ll>mp;
ll pref[1000001],suff[1000001],pref2[1000001],suff2[1000001];
int main()
{
//ios_base::sync_with_stdio(0);cin.tie(0);
//freopen (".in","r",stdin);
//freopen (".out","w",stdout);
scanf("%d",&N);
for (ll i=1;i<=N;i++){
ll Y;
scanf("%d%d",&Y,&L[i]);
ll x=i,y=Y;
if (x>y) swap(x,y);
mp[{x,y}]=max(mp[{x,y}],L[i]);
}
for (auto it:mp){
//cout<<"edge: "<<it.first.first<<' '<<it.first.second<<endl;
adj[it.first.first].push_back({it.first.second,it.second});
adj[it.first.second].push_back({it.first.first,it.second});
}
for (ll i=1;i<=N;i++)
if (!vis[i]){
//cout<<"Component: "<<i<<endl;
cycle.clear();
adjDis.clear();
deepest.clear();
findCycle(i,i);
/*
cout<<"Cycle: ";
for (ll x:cycle)
cout<<x<<' ';
cout<<endl;
*/
if (cycle.size()==0){
//cout<<"multiEdge: "<<findDiameter(i)<<endl;
ans+=findDiameter(i);
continue;
}
maxCur=0;
ll C=cycle.size();
for (ll i=0;i<C;i++){
pref[i]=0;
suff[i]=0;
pref2[i]=0;
suff2[i]=0;
ll inFront=cycle[(i+1)%C];
ll inBack=cycle[(i-1+C)%C];
adjDis.push_back(mp[{min(cycle[i],inFront),max(cycle[i],inFront)}]);
bad=inFront;
bad2=inBack;
maxCur=max(maxCur,findDiameter(cycle[i]));
deepest.push_back(getDeep(cycle[i],cycle[i],0));
}
for (ll i=0;i<C;i++){
if (i>0){
pref[i]=pref[i-1]+adjDis[i-1];
pref2[i]=max(pref2[i-1],pref[i]+deepest[i]);
}
else
pref2[i]=deepest[i];
}
/*
cout<<"deepest: "<<' ';
for (ll x:deepest)
cout<<x<<' ';
cout<<endl;
cout<<"adjDis: "<<' ';
for (ll x:adjDis)
cout<<x<<' ';
cout<<endl;
cout<<"pref: ";
for (ll i=0;i<C;i++)
cout<<pref[i]<<' ';
cout<<endl;
*/
for (ll i=C-1;i>=0;i--){
if (i+1<C){
suff[i]=suff[i+1]+adjDis[i];
suff2[i]=max(suff2[i+1],suff[i]+deepest[i]);
}
else
suff2[i]=deepest[i];
}
for (ll i=0;i+1<C;i++){
//cout<<i<<": "<<adjDis.back()<<' '<<pref2[i]<<' '<<suff2[i+1]<<endl;
maxCur=max(maxCur,adjDis.back()+pref2[i]+suff2[i+1]);
}
ll sweep=0;
for (ll 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;
}
cout<<ans<<endl;
return 0;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:80:16: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
scanf("%d",&N);
~~^
islands.cpp:83:26: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
scanf("%d%d",&Y,&L[i]);
~~ ^
islands.cpp:83:26: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
islands.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
~~~~~^~~~~~~~~
islands.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&Y,&L[i]);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
48124 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
45 ms |
48072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
45 ms |
48120 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
45 ms |
48128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
46 ms |
47992 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
45 ms |
47992 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
46 ms |
48000 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
47 ms |
47992 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
45 ms |
47992 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
45 ms |
48000 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
45 ms |
47996 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
48120 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 |
48 ms |
48376 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 |
56 ms |
50296 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 |
76 ms |
55296 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 |
184 ms |
76792 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 |
325 ms |
105336 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 |
854 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 |
848 ms |
131072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
