| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 503452 | hellowsdf | Islands (IOI08_islands) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//
// Created by Kevin Lyu on 2022-01-07.
//
#include "bits/stdc++.h"
using namespace std;
const int size = 1e6+5;
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
const int MN = 1e6+1;
bool visited[MN];
vector<pair<int,int>>cycles;
//deque<pair<long long,int>>dq; // value, pos
long long mxLen[MN];
vector<int> par;
pair<long long,int>dq[MN];
long long res;
long long longestDiameter = 0;
long long dist = 0;
queue<pair<int,int>>todo;
int front = -1;
int rear = 0;
long long dis[MN];
bool isEmpty ()
{
return (front == -1);
}
void insertrear(pair<long long,int> key)
{
if (front == -1)
{
front = 0;
rear = 0;
}
else if (rear == size-1)
rear = 0;
// increment rear end by '1'
else
rear = rear+1;
// insert current element into Deque
dq[rear] = key ;
}
// Deletes element at front end of Deque
void deletefront()
{
if (front == rear)
{
front = -1;
rear = -1;
}
else
if (front == size -1)
front = 0;
else // increment front by '1' to remove current
// front value from Deque
front = front+1;
}
// Delete element at rear end of Deque
void deleterear()
{
if (front == rear)
{
front = -1;
rear = -1;
}
else if (rear == 0)
rear = size-1;
else
rear = rear-1;
}
pair<long long,int> getFront()
{
return dq[front];
}
pair<long long,int> getRear()
{
return dq[rear];
}
int find(int a){
if(a!=par[a]){
return par[a] = find(par[a]);
}
return a;
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a!=b){
par[a] = b;
}
}
struct Edge{
int v,w,id,next;
};
int head[MN*2];
Edge edges[MN*2];
int tot = 0;
void add(int x, int y, int id, int weight){
edges[++tot] = {y,weight,id,head[x]};
head[x] = tot;
}
pair<long long,int> getDepth(int node, int parent, pair<int,int> beside){
todo.push({node,-1});
long long mx = 0;
int v = 0;
dis[node] = 0;
while(!todo.empty()){
auto task = todo.front();
if(mx<dis[task.first]){
mx = dis[task.first];
v = task.first;
}
todo.pop();
for(int i = head[task.first]; i; i = edges[i].next){
if(!(edges[i].v == task.second or edges[i].v == beside.first or edges[i].v == beside.second)){
dis[edges[i].v] = dis[task.first]+edges[i].w;
todo.push({edges[i].v,task.first});
}
}
}
return {mx,v};
}
bool dfsCycle(int node, int parent,vector<pair<int,int>>&temp){
visited[node] = true;
for(int i = head[node]; i; i = edges[i].next){
if(!visited[edges[i].v]){
if(dfsCycle(edges[i].v,edges[i].id,temp)){
temp.push_back({node,edges[i].w});
return true;
}
}else{
if(parent!=edges[i].id){
temp.push_back({node,edges[i].w});
return true;
}
}
}
return false;
}
long long ans = 0;
int main(){
int n;
scan(n);
par.resize(n+1);
for(int i = 1;i<=n;i++){
par[i] = i;
}
for(int i = 1;i<=n;i++){
int a,w;
scan(a);
scan(w);
merge(i,a);
add(i,a,i,w);
add(a,i,i,w);
}
for(int i = 1;i<=n;i++){
if(i == find(i)){
cycles.clear();
dfsCycle(i,-1,cycles);
cycles.push_back({cycles[0]});
cycles.erase(cycles.begin());
longestDiameter = 0;
reverse(cycles.begin(),cycles.end());
for(int j = 0;j<cycles.size();j++){ // for every node in the cycle of the component
auto task = getDepth(cycles[j].first,-1,make_pair(cycles[j == 0?cycles.size()-1:j-1].first,cycles[j == cycles.size()-1?0:j+1].first));
mxLen[j] =task.first;
int far = task.second;
longestDiameter = max(longestDiameter,getDepth(far,-1,make_pair(cycles[j == 0?cycles.size()-1:j-1].first,cycles[j == cycles.size()-1?0:j+1].first)).first);
}
res = longestDiameter;
int pos;
front = -1;
rear = 0;
dist = 0;
for(int j = 0;j<cycles.size()*2;j++){
pos = j%cycles.size();
if(!isEmpty()){
res = max(res,dist+mxLen[pos]+getFront().first);
}
long long v = mxLen[pos]-dist;
while(!isEmpty() and v>getRear().first){
deleterear();
}
insertrear({v,j});
while(!isEmpty() and getFront().second<=(int)(j-cycles.size()+1)){
deletefront();
}
dist+=cycles[pos].second;
}
ans+=res;
}
}
if(a)
cout<<ans<<endl;
}