#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
{
int F,S,num;
};
vector<mode> G[1000005];
vector<pll> cir;
vector<ll> len;
bitset<1000005> yc;
ll M,dft,dfn[1000005];
const ll INF=1e18;
bool dfs(int u,int f)
{
int flag=0;
dfn[u]=++dft;
for(auto i:G[u])
if(i.num!=f)
if(!dfn[i.F])
if(dfs(i.F,i.num))
flag=1,len.pb(i.S);
else;
else if(dfn[i.F]<dfn[u])
flag=1,yc[i.F]=1,cir.pb(MP(i.F,0)),len.pb(i.S);
if(flag)
if(yc[u]) flag=0;
else cir.pb(MP(u,0)),yc[u]=1;
return flag;
}
ll dfs2(int 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()
{jizz
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}),G[a].pb(mode{i,w,i});
for(int i=1;i<=n;++i)
if(!dfn[i])
{
cir.clear(),len.clear(),M=0,dfs(i,i);
for(int j=0;j<cir.size();++j)
cir[j].S=dfs2(cir[j].F);
int n=cir.size();
deque<pll> dq;
sum=0,dq.pb(MP(0,cir[0].S));
for(int j=0;j<n;++j)
cir.pb(cir[j]),len.pb(len[j]);
for(int 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(int, int)':
islands.cpp:33:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if(i.num!=f)
^
islands.cpp:40:4: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if(flag)
^
islands.cpp: In function 'int main()':
islands.cpp:66:35: warning: narrowing conversion of 'a' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
cin >> a >> w,G[i].pb(mode{a,w,i}),G[a].pb(mode{i,w,i});
^
islands.cpp:66:35: warning: narrowing conversion of 'w' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
islands.cpp:66:56: warning: narrowing conversion of 'w' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
cin >> a >> w,G[i].pb(mode{a,w,i}),G[a].pb(mode{i,w,i});
^
islands.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<cir.size();++j)
~^~~~~~~~~~~
islands.cpp:78:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=1;j<cir.size();++j)
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 2 |
Runtime error |
49 ms |
47608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Correct |
22 ms |
24064 KB |
Output is correct |
| 4 |
Runtime error |
49 ms |
47608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 6 |
Incorrect |
22 ms |
23808 KB |
Output isn't correct |
| 7 |
Incorrect |
22 ms |
23780 KB |
Output isn't correct |
| 8 |
Runtime error |
48 ms |
47608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Incorrect |
22 ms |
23808 KB |
Output isn't correct |
| 10 |
Runtime error |
48 ms |
47480 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Correct |
22 ms |
23928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
47584 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 |
49 ms |
47656 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 |
49016 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 |
68 ms |
52588 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 |
115 ms |
66600 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 |
177 ms |
51196 KB |
Output is correct |
| 2 |
Runtime error |
224 ms |
97488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
370 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 |
437 ms |
131072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
