#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,v,w,vis[100005],path,ans,ct;
pair<int,int> dist[100005];
struct vertex{
int x,dw,rw;//dw is the discretized weight, rw is the original weight
};
vector<vertex> g[100005];
map<int,int> dis;
vector<int> clr,edge;
priority_queue<pair<int,int>> q;
void dij(int oof)
{
q.push({0,oof});
dist[oof].first=0;
while (q.size()){
v=q.top().second;
q.pop();
if (vis[v]) continue;
vis[v]=1;
//cout<<v<<"\n";
clr.push_back(v);
for (auto i:g[v]){
if (dist[i.x].first>dist[v].first+i.dw){
// cout<<i.x<<"\n";
dist[i.x].first=dist[v].first+i.dw;
dist[i.x].second=dist[v].second+i.rw;
q.push({dist[i.x].first,i.x});
}
}
}
}
signed main()
{
cin>>n;
for (int i=1;i<=n;i++){
cin>>v>>w;
g[i].push_back((vertex){v,0,w});
g[v].push_back((vertex){i,0,w});
edge.push_back(w);
}
sort(edge.begin(),edge.end());
reverse(edge.begin(),edge.end());
for (int i:edge) if (!dis[i]) dis[i]=++ct;
for (int i=1;i<=n;i++){
for (int j=0;j<g[i].size();j++){
g[i][j].dw=dis[g[i][j].rw];
}
}
for (int i=1;i<=n;i++) dist[i].first=1e18;
for (int i=1;i<=n;i++){
if (!vis[i]) {
dij(i);
int mx=0,node=0;
for (int i:clr) {
if (dist[i].second>mx) mx=dist[i].second,node=i;
vis[i]=0,dist[i]={1e18,0};
}
path=0;
dij(node);
for (int i:clr) path=max(path,dist[i].second);
clr.clear();
ans+=path;
// cout<<path<<"\n";
}
}
cout<<ans<<"\n";
}
//for each connected component find the tree diameter,and travel to next subgraph?
//dijstra with longest path?no good, there is nothing call longest dijstra...
//love to do graph questions, at the same time hate don't no how to solve graph questions..
//sort the edges by non-increasing order, and distrecitze the edges by weight from small to large
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:47:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int j=0;j<g[i].size();j++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
2732 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 10 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
10808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
340 ms |
49848 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
165 ms |
38832 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5068 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
7816 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
