| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 120185 | 2019-06-23T16:57:14 Z | arthurconmy | Islands (IOI08_islands) | C++17 | 0 ms | 0 KB |
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef pair<int,int> pii;
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
#define REPb(j, d, c) for (int j = int(d); j >= int(c); j--)
#define ff first
#define ss second
#define pb push_back
#define len(x) int((x).size())
#define endl "\n"
const int MAXN=1 + 1e6;
int n;
tuple<int,int,int> edges[MAXN]; // vertex one, vertex two, length
vector<tuple<int,int,int>> adj[MAXN]; // destination edge, length, edge no.
bool edge_used[MAXN];
int cycle_edge;
bool vis1[MAXN];
bool in_cycle[MAXN];
ll length_to[MAXN];
vector<int> cur_comp;
int parent[MAXN];
void connect_dfs(int v)
{
for(auto u:adj[v])
{
if(vis1[get<0>(u)])
{
if(!edge_used[get<2>(u)] && cycle_edge==-1) cycle_edge=get<2>(u);
continue;
}
cur_comp.pb(get<0>(u));
vis1[get<0>(u)]=true;
edge_used[get<2>(u)]=true;
connect_dfs(get<0>(u));
}
}
/*
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
*/
int main() // LL OR INT?? DELETED IFSTREAM??
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//ifstream cin("input.txt");
//ifstream cin("test.in");
//ofstream cout("test.out");
// take input
cin>>n;
REP(u,1,n)
{
int v, l;
cin>>v>>l;
adj[u].pb({v,l,u});
adj[v].pb({u,l,u});
edges[u]={u,v,l};
}
ll ans=0;
REP(i,1,n)
{
// for connected component
// find cycle
if(vis1[i]) continue;
cur_comp.clear();
cur_comp.pb(i);
vis1[i]=true;
cycle_edge=-1;
connect_dfs(i);
// for(auto v:cur_comp) cout << v << " ";
// cout << endl;
// find simple path between vertices of the cycle edge in the tree excepting the cycle edge
// vi parent(cur_comp.size()+1);
vi BFS = {get<0>(edges[cycle_edge])};
while(!BFS.empty())
{
vi new_BFS;
for(auto u:BFS)
{
for(auto v:adj[u])
{
if(get<2>(v)==cycle_edge || parent[get<0>(v)]) continue;
parent[get<0>(v)] = u;
length_to[get<0>(v)] = get<1>(v);
new_BFS.pb(get<0>(v));
}
}
BFS=new_BFS;
}
vi cycle={get<1>(edges[cycle_edge])}; // this is kinda done in reverse...
in_cycle[cycle[0]]=true;
vector<int> path_len;
while(cycle.back() != get<0>(edges[cycle_edge]))
{
path_len.pb(length_to[cycle.back()]);
cycle.pb(parent[cycle.back()]);
in_cycle[cycle.back()]=true;
}
path_len.pb(get<2>(edges[cycle_edge]));
// for(auto c:cycle) cout << c << " ";
// cout << endl;
// for(auto pl:path_len) cout << pl << " ";
// cout << endl << endl;
// for each branch
vector<ll> branch_len(cycle.size());
REP(i,0,cycle.size()-1)
{
vector<pair<int,ll>> BFS2 = {{cycle[i],0}};
ll max_dis=0;
while(!BFS2.empty())
{
vector<pair<int,ll>> new_BFS2;
for(auto u:BFS2)
{
for(auto v:adj[u.ff])
{
int vert = get<0>(v);
if(in_cycle[vert]) continue;
in_cycle[vert]=true;
max_dis=max(max_dis,u.ss + ll(get<1>(v)));
new_BFS2.pb({vert, u.ss + ll(get<1>(v)}));
}
}
BFS2=new_BFS2;
}
// cout << cycle[i] << " " << max_dis << endl;
branch_len[i] = max_dis;
}
// do the PQ DP thing
priority_queue<pair<ll,int>> endps;
ll lap=0;
ll max_trip=0;
REP(i,0,cycle.size()-1)
{
if(i>0) lap+=path_len[i-1];
if(!endps.empty()) max_trip=max(max_trip,endps.top().ff+branch_len[i]+lap);
endps.push({branch_len[i]-lap,i});
// cout << i << " " << max_trip << endl;
}
lap+=path_len.back();
REP(i,0,cycle.size()-1)
{
while(!endps.empty() && endps.top().ss<=i) endps.pop();
if(i>0) lap+=path_len[i-1];
if(!endps.empty()) max_trip=max(max_trip,endps.top().ff+branch_len[i]+lap);
}
// cout << "MAX_TRIP: " << max_trip << endl;
ans += max_trip;
}
// find length
// gravy
cout << ans << endl;
}