#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
#include <assert.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 1000007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
vector < pair < ll, pair <int,int> > > edges;
vector < pair <int,ll> > adj[M];
vector <int> nodes;
pair <int,int> edge;
ll n, cost[M], mxchild[M], p[M], ans, edgecost, root, time;
bool vist[M];
void get(int node)
{
assert(time < 1e5);
++time;
nodes.pb(node);
vist[node] = 1;
for(auto i : adj[node]){
edges.pb({i.S, {node, i.F}});
if(!vist[i.F]) get(i.F);
}
return;
}
void dfs(int node, ll cur)
{
// cout << node << " " << edge.F << " " << edge.S << endl;
assert(time < 1e5);
++time;
cost[node] = cur;
mxchild[node] = cur;
for(auto i : adj[node]){
if(i.F == p[node] || ((edge == make_pair(node, i.F) || edge == make_pair(i.F, node)) && edgecost == i.S)) continue;
p[i.F] = node;
dfs(i.F, cur + i.S);
mxchild[node] = max(mxchild[node], mxchild[i.F]);
}
return;
}
pair <int,int> calc(int node)
{
assert(time < 1e5);
++time;
pair <ll,ll> ret;
int cur = node;
while(p[cur] != root) cur = p[cur];
ret.F = cost[node] - cost[cur];
ret.S = mxchild[node];
return ret;
}
ll best(int node)
{
ll ret = 0;
for(auto i : adj[node]){
if(i.F == p[node]) continue;
if(i.F == edge.F || i.F == edge.S) return -1;
ll x = best(i.F);
if(x == -1 && node != 1) return -1;
else ret = max(ret, best(i.F));
}
return ret;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i){
ll x, y;
cin >> x >> y;
// x = (i % n) + 1;
// y = i;
adj[x].pb({i, y});
adj[i].pb({x, y});
}
for(int j = 1; j <= n; ++j){
if(vist[j]) continue;
time = 0;
get(j);
sort(all(edges), greater < pair < ll, pair <int,int> > > ());
edge = {edges.back().S.F, edges.back().S.S};
edgecost = edges.back().F;
root = 0;
for(auto i : nodes) if(i != edge.F && i != edge.S) {root = i; break;}
if(root == 0){
// for(auto i : edges) cout << i.S.F << " " << i.S.S << " " << i.F << endl;
ans += edges[0].F;
continue;
}
dfs(root, 0);
ll mx1 = 0, mx2 = 0, mx = 0;
for(auto i : nodes){
if(cost[i] > mx1) mx2 = mx1, mx1 = cost[i];
else if(cost[i] > mx2) mx2 = cost[i];
}
mx = mx1 + mx2;
mx1 = best(root);
pair <ll,ll> nodea = calc(edge.F);
pair <ll,ll> nodeb = calc(edge.S);
mx = max(mx, nodea.F + nodeb.S + edges.back().F);
mx = max(mx, nodea.F + nodeb.F + edges.back().F);
mx = max(mx, nodea.S + nodeb.F + edges.back().F);
mx = max(mx, nodea.S + nodeb.S + edges.back().F);
mx = max(mx, mx1 + cost[edge.F] + nodeb.S + edges.back().F);
mx = max(mx, mx1 + cost[edge.F] + nodeb.F + edges.back().F);
mx = max(mx, mx1 + nodea.F + cost[edge.S] + edges.back().F);
mx = max(mx, mx1 + nodea.S + cost[edge.S] + edges.back().F);
ans += mx;
edges.clear();
nodes.clear();
}
assert(time > 1e7) ;
cout << ans << endl;
return 0;
}
Compilation message
islands.cpp:31:55: error: 'll time' redeclared as different kind of entity
31 | ll n, cost[M], mxchild[M], p[M], ans, edgecost, root, time;
| ^~~~
In file included from /usr/include/pthread.h:23,
from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:35,
from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
from /usr/include/c++/10/ext/atomicity.h:35,
from /usr/include/c++/10/bits/ios_base.h:39,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from islands.cpp:1:
/usr/include/time.h:75:15: note: previous declaration 'time_t time(time_t*)'
75 | extern time_t time (time_t *__timer) __THROW;
| ^~~~
In file included from islands.cpp:13:
islands.cpp: In function 'void get(int)':
islands.cpp:36:17: error: invalid operands of types 'time_t(time_t*) throw ()' {aka 'long int(long int*)'} and 'double' to binary 'operator<'
36 | assert(time < 1e5);
| ~~~~ ^ ~~~
| | |
| | double
| time_t(time_t*) throw () {aka long int(long int*)}
islands.cpp:37:7: warning: ISO C++ forbids incrementing a pointer of type 'time_t (*)(time_t*) throw ()' {aka 'long int (*)(long int*)'} [-Wpointer-arith]
37 | ++time;
| ^~~~
islands.cpp:37:7: error: lvalue required as increment operand
In file included from islands.cpp:13:
islands.cpp: In function 'void dfs(int, ll)':
islands.cpp:50:13: error: invalid operands of types 'time_t(time_t*) throw ()' {aka 'long int(long int*)'} and 'double' to binary 'operator<'
50 | assert(time < 1e5);
| ~~~~ ^ ~~~
| | |
| | double
| time_t(time_t*) throw () {aka long int(long int*)}
islands.cpp:51:7: warning: ISO C++ forbids incrementing a pointer of type 'time_t (*)(time_t*) throw ()' {aka 'long int (*)(long int*)'} [-Wpointer-arith]
51 | ++time;
| ^~~~
islands.cpp:51:7: error: lvalue required as increment operand
In file included from islands.cpp:13:
islands.cpp: In function 'std::pair<int, int> calc(int)':
islands.cpp:65:17: error: invalid operands of types 'time_t(time_t*) throw ()' {aka 'long int(long int*)'} and 'double' to binary 'operator<'
65 | assert(time < 1e5);
| ~~~~ ^ ~~~
| | |
| | double
| time_t(time_t*) throw () {aka long int(long int*)}
islands.cpp:66:7: warning: ISO C++ forbids incrementing a pointer of type 'time_t (*)(time_t*) throw ()' {aka 'long int (*)(long int*)'} [-Wpointer-arith]
66 | ++time;
| ^~~~
islands.cpp:66:7: error: lvalue required as increment operand
islands.cpp: In function 'int main()':
islands.cpp:102:14: error: assignment of function 'time_t time(time_t*)'
102 | time = 0;
| ~~~~~^~~
In file included from islands.cpp:13:
islands.cpp:136:17: error: invalid operands of types 'time_t(time_t*) throw ()' {aka 'long int(long int*)'} and 'double' to binary 'operator>'
136 | assert(time > 1e7) ;
| ~~~~ ^ ~~~
| | |
| | double
| time_t(time_t*) throw () {aka long int(long int*)}
