#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1000005
#define II pair <int,int>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
vector <int> a[N];
struct edge { int u,v,k; };
edge e[N];
int tr[N],trc[N],cycle[N];
bool incycle[N],visited[N];
ll n,i,u,v,k,c[N],dis[N],ncycle,sum,res;
const ll oo=round(1e18);
struct Fenwick_Tree
{
ll bit[N],d[N],n;
void Init(int _n)
{
n=_n;
for(int i=1;i<=n;i++) bit[i]=d[i]=-oo;
}
void update(int i,ll k)
{
d[i]=max(d[i],k);
while(i<=n) bit[i]=max(bit[i],k),i+=(i & -i);
}
ll get(int l,int r)
{
ll res=-oo,i=r;
while(i>=l)
if(i-(i & -i)>=l) res=max(res,bit[i]),i-=(i & -i);
else res=max(res,d[i]),i--;
return res;
}
} FT;
void dfs(int u)
{
visited[u]=1;
for(int adj:a[u])
{
int v=(e[adj].u==u ? e[adj].v : e[adj].u);
if(visited[v]==0) dfs(v);
}
}
void Find_cycle(int u,int x)
{
for(int adj:a[u])
{
if(adj==x) continue;
int v=v=(e[adj].u==u ? e[adj].v : e[adj].u),k=e[adj].k;
if(tr[v]==0)
{
tr[v]=u; trc[v]=k;
Find_cycle(v,adj);
}
else if(ncycle==0)
{
sum=0;
while(u!=v)
{
cycle[++ncycle]=u; incycle[u]=1;
dis[ncycle]=sum; sum+=trc[u];
u=tr[u];
}
cycle[++ncycle]=u; incycle[u]=1;
dis[ncycle]=sum; sum+=k;
return ;
}
}
}
/////////////////////////////////////////////////////////////////////////////
ll cal(int u,int p,ll &ma)
{
ll res=0,ma0=0,ma1=0;
for(int adj:a[u])
{
int v=v=(e[adj].u==u ? e[adj].v : e[adj].u);;
if(v!=p && incycle[v]==0)
{
ll k=cal(v,u,ma)+e[adj].k;
res=max(res,k);
if(ma0<k) ma0=k;
if(ma1<ma0) swap(ma1,ma0);
}
}
ma=max(ma,ma0+ma1);
return res;
}
ll Work()
{
int i,u,v;
FT.Init(ncycle);
ll res=0;
for(i=1;i<=ncycle;i++)
{
u=cycle[i];
c[i]=cal(u,0,res);
FT.update(i,c[i]-dis[i]);
}
for(i=1;i<ncycle;i++)
{
int l=i,r=ncycle;
while(l<r)
{
int mid=(l+r+1)>>1;
if(sum-(dis[mid]-dis[i])>=dis[mid]-dis[i])
l=mid;
else r=mid-1;
}
res=max(res,c[i]+sum+dis[i]+FT.get(i+1,l));
}
FT.Init(ncycle);
for(i=1;i<=ncycle;i++)
{
u=cycle[i];
FT.update(i,c[i]+dis[i]);
}
for(i=1;i<ncycle;i++)
{
int l=i,r=ncycle;
while(l<r)
{
int mid=(l+r+1)>>1;
if(sum-(dis[mid]-dis[i])>=dis[mid]-dis[i])
l=mid;
else r=mid-1;
}
res=max(res,c[i]-dis[i]+FT.get(l+1,ncycle));
}
return res;
}
int main()
{
//freopen("islands.inp","r",stdin);
// freopen("islands.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(u=1;u<=n;u++)
{
cin>>v>>k;
a[u].push_back(u); a[v].push_back(u);
e[u]={ u,v,k };
}
for(u=1;u<=n;u++)
if(visited[u]==0)
{
dfs(u);
tr[u]=-1;
ncycle=0;
Find_cycle(u,0);
res+=Work();
}
cout<<res;
}
Compilation message
islands.cpp: In function 'void Find_cycle(int, int)':
islands.cpp:62:16: warning: operation on 'v' may be undefined [-Wsequence-point]
62 | int v=v=(e[adj].u==u ? e[adj].v : e[adj].u),k=e[adj].k;
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp: In function 'long long int cal(int, int, long long int&)':
islands.cpp:91:16: warning: operation on 'v' may be undefined [-Wsequence-point]
91 | int v=v=(e[adj].u==u ? e[adj].v : e[adj].u);;
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp: In function 'long long int Work()':
islands.cpp:105:13: warning: unused variable 'v' [-Wunused-variable]
105 | int i,u,v;
| ^
islands.cpp: In function 'int main()':
islands.cpp:158:16: warning: narrowing conversion of 'u' from 'long long int' to 'int' [-Wnarrowing]
158 | e[u]={ u,v,k };
| ^
islands.cpp:158:18: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
158 | e[u]={ u,v,k };
| ^
islands.cpp:158:20: warning: narrowing conversion of 'k' from 'long long int' to 'int' [-Wnarrowing]
158 | e[u]={ u,v,k };
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
41308 KB |
Output is correct |
2 |
Correct |
7 ms |
41308 KB |
Output is correct |
3 |
Correct |
7 ms |
41564 KB |
Output is correct |
4 |
Correct |
7 ms |
41308 KB |
Output is correct |
5 |
Correct |
7 ms |
41308 KB |
Output is correct |
6 |
Correct |
7 ms |
41436 KB |
Output is correct |
7 |
Correct |
7 ms |
41440 KB |
Output is correct |
8 |
Correct |
7 ms |
41308 KB |
Output is correct |
9 |
Correct |
7 ms |
41532 KB |
Output is correct |
10 |
Correct |
7 ms |
41308 KB |
Output is correct |
11 |
Correct |
7 ms |
41308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
41564 KB |
Output is correct |
2 |
Correct |
7 ms |
41412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
41564 KB |
Output is correct |
2 |
Correct |
8 ms |
41692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
42076 KB |
Output is correct |
2 |
Correct |
21 ms |
45916 KB |
Output is correct |
3 |
Correct |
15 ms |
42216 KB |
Output is correct |
4 |
Correct |
10 ms |
41820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
46936 KB |
Output is correct |
2 |
Correct |
42 ms |
48468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
65 ms |
52200 KB |
Output is correct |
2 |
Correct |
95 ms |
63572 KB |
Output is correct |
3 |
Correct |
115 ms |
72160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
130 ms |
63064 KB |
Output is correct |
2 |
Correct |
178 ms |
89168 KB |
Output is correct |
3 |
Correct |
266 ms |
99156 KB |
Output is correct |
4 |
Correct |
287 ms |
116712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
190 ms |
89012 KB |
Output is correct |
2 |
Runtime error |
553 ms |
131072 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
274 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |