//
// 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;
}
}
cout<<ans<<endl;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:184:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for(int j = 0;j<cycles.size();j++){ // for every node in the cycle of the component
| ~^~~~~~~~~~~~~~
islands.cpp:185:117: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
185 | 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));
| ~~^~~~~~~~~~~~~~~~~~
islands.cpp:188:131: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
188 | 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);
| ~~^~~~~~~~~~~~~~~~~~
islands.cpp:195:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for(int j = 0;j<cycles.size()*2;j++){
| ~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
316 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
320 KB |
Output is correct |
| 5 |
Correct |
0 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
0 ms |
332 KB |
Output is correct |
| 8 |
Correct |
0 ms |
332 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
0 ms |
332 KB |
Output is correct |
| 11 |
Correct |
0 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1480 KB |
Output is correct |
| 2 |
Correct |
9 ms |
4304 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1612 KB |
Output is correct |
| 4 |
Correct |
3 ms |
932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
5980 KB |
Output is correct |
| 2 |
Correct |
20 ms |
9000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
14840 KB |
Output is correct |
| 2 |
Correct |
43 ms |
23084 KB |
Output is correct |
| 3 |
Correct |
61 ms |
37316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
27064 KB |
Output is correct |
| 2 |
Correct |
91 ms |
52320 KB |
Output is correct |
| 3 |
Correct |
106 ms |
67276 KB |
Output is correct |
| 4 |
Correct |
141 ms |
95188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
71312 KB |
Output is correct |
| 2 |
Correct |
358 ms |
130444 KB |
Output is correct |
| 3 |
Correct |
135 ms |
51520 KB |
Output is correct |
| 4 |
Correct |
188 ms |
96936 KB |
Output is correct |
| 5 |
Correct |
187 ms |
95040 KB |
Output is correct |
| 6 |
Correct |
631 ms |
61544 KB |
Output is correct |
| 7 |
Runtime error |
358 ms |
131072 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
73936 KB |
Output is correct |
| 2 |
Correct |
134 ms |
62660 KB |
Output is correct |
| 3 |
Runtime error |
139 ms |
131076 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
