#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
struct mode
{
ll F,S,num;
};
struct dfss
{
ll flag,u,f,ln;
vector<dfss>::iterator rtto;
};
vector<mode> G[1000005];
vector<pll> cir;
vector<ll> len;
bitset<1000005> yc;
ll M,dft,dfn[1000005],cur[1000005];
const ll INF=1e18;
bool dfs(ll u,ll f)
{
vector<dfss> st;
st.pb(dfss{0,u,f,0,vector<dfss>::iterator()});
while(!st.empty())
{
auto &d=st.back();
vector<dfss>::iterator tp=--st.end();
if(!~cur[d.u])
++cur[d.u],d.flag=0,dfn[d.u]=++dft;
for(ll &i=cur[d.u];i<G[d.u].size();++i)
if(G[d.u][i].num!=d.f)
if(!dfn[G[d.u][i].F])
{
st.pb(dfss{0,G[d.u][i].F,G[d.u][i].num,G[d.u][i].S,tp});
goto nxt;
}
else if(dfn[G[d.u][i].F]<=dfn[d.u])
d.flag=1,yc[G[d.u][i].F]=1,cir.pb(MP(G[d.u][i].F,0)),len.pb(G[d.u][i].S);
st.pop_back();
if(d.flag)
if(yc[d.u]) d.flag=0;
else cir.pb(MP(d.u,0)),len.pb(d.ln),yc[d.u]=1;
if(d.flag&&d.u!=u)
d.rtto->flag=1;
nxt:
;
}
}
ll dfs2(ll u)
{
ll mx=0,sx=0;
yc[u]=1;
for(auto i:G[u])
if(!yc[i.F])
{
ll d=dfs2(i.F)+i.S;
if(d>mx) sx=mx,mx=d;
else if(d>sx) sx=d;
}
M=max(M,sx+mx);
return mx;
}
int main()
{
ll n,a,w,ans=0,sum;
cin >> n;
for(int i=1;i<=n;++i)
{
cin >> a >> w;
G[i].pb(mode{a,w,i});
if(a!=i) G[a].pb(mode{i,w,i});
}
MEM(cur,-1);
for(int i=1;i<=n;++i)
if(!dfn[i])
{
cir.clear(),len.clear(),M=0,dfs(i,-1);
for(ll j=0;j<cir.size();++j)
cir[j].S=dfs2(cir[j].F);
if(cir.size()>1)
{
ll n=cir.size();
deque<pll> dq;
sum=0,dq.pb(MP(0,cir[0].S));
for(ll j=0;j<n;++j)
cir.pb(cir[j]),len.pb(len[j]);
for(ll j=1;j<cir.size();++j)
{
while(dq.size()&&j-dq[0].F>=n) dq.pop_front();
sum+=len[j-1],M=max(M,sum+cir[j].S+dq[0].S);
while(dq.size()&&cir[j].S-sum>=dq.back().S)
dq.pop_back();
dq.pb(MP(j,cir[j].S-sum));
}
}
ans+=M;
}
cout << ans << "\n";
}
Compilation message
islands.cpp: In function 'bool dfs(ll, ll)':
islands.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll &i=cur[d.u];i<G[d.u].size();++i)
~^~~~~~~~~~~~~~
islands.cpp:45:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if(G[d.u][i].num!=d.f)
^
islands.cpp:54:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if(d.flag)
^
islands.cpp:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
islands.cpp: In function 'int main()':
islands.cpp:94:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=0;j<cir.size();++j)
~^~~~~~~~~~~
islands.cpp:103:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=1;j<cir.size();++j)
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
31608 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
31616 KB |
Output isn't correct |
| 3 |
Incorrect |
30 ms |
31736 KB |
Output isn't correct |
| 4 |
Runtime error |
63 ms |
63096 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Incorrect |
30 ms |
31608 KB |
Output isn't correct |
| 6 |
Runtime error |
64 ms |
63096 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
65 ms |
63244 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Incorrect |
29 ms |
31608 KB |
Output isn't correct |
| 9 |
Runtime error |
64 ms |
63224 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Correct |
30 ms |
31616 KB |
Output is correct |
| 11 |
Runtime error |
64 ms |
63096 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
31736 KB |
Output is correct |
| 2 |
Runtime error |
98 ms |
63452 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
67 ms |
63496 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 |
84 ms |
66248 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 |
117 ms |
73064 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 |
248 ms |
94612 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 |
414 ms |
118264 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 |
Correct |
898 ms |
95056 KB |
Output is correct |
| 2 |
Runtime error |
1441 ms |
131072 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 |
931 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
