#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, timer;
bool vist[M];
void get(int node)
{
++timer;
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;
++timer;
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)
{
++timer;
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;
timer = 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(timer > 1e7);
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2085 ms |
23756 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2074 ms |
23796 KB |
Time limit exceeded |
| 3 |
Runtime error |
30 ms |
48332 KB |
Execution killed with signal 6 |
| 4 |
Execution timed out |
2070 ms |
23756 KB |
Time limit exceeded |
| 5 |
Runtime error |
73 ms |
131076 KB |
Execution killed with signal 9 |
| 6 |
Execution timed out |
2077 ms |
23756 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2077 ms |
23756 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2054 ms |
23756 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2075 ms |
23756 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2083 ms |
23756 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2087 ms |
23756 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
48420 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
256 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
74 ms |
63780 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
353 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
169 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
505 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
328 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
