#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define F first
#define S second
#define chmin(a,b) a=(a<b?a:b)
#define chmax(a,b) a=(a>b?a:b)
const int mxn=1e5+5;
vector<pair<int,int>>adj[mxn];
pair<int,int>dp[mxn];
bool vis[mxn];
int dp2[mxn];
void dfs(int v,int pa){
vis[v]=1;
for(auto [u,len]:adj[v]){
if(u==pa)
continue;
dfs(u,v);
if(dp[v].F<=dp[u].F+len){
dp[v].S=dp[v].F;
dp[v].F=dp[u].F+len;
}
else if(dp[v].S<dp[u].F+len){
dp[v].S=dp[u].F+len;
}
}
}
pair<int,int> mn;
int mx=-2e9;
void reroot(int v,int pa){
chmin(mn,make_pair(dp[v].F,v));
for(auto [u,len]:adj[v]){
if(u==pa)
continue;
int x;
if(dp[v].F!=dp[u].F+len){
x=dp[v].F;
}
else{
x=dp[v].S;
}
x+=len;
if(dp[u].F<=x){
dp[u].S=dp[u].F;
dp[u].F=x;
}
else if(dp[u].S<x){
dp[u].S=x;
}
reroot(u,v);
}
}
void dfs2(int v,int pa){
for(auto [u,len]:adj[v]){
if(u==pa)
continue;
dfs2(u,v);
chmax(mx,dp2[v]+dp2[u]+len);
chmax(dp2[v],dp2[u]+len);
}
}
vector<pair<int,int>>v;
int travelTime(int n,int m,int l,int a[],int b[],int t[]){
for(int i=0;i<m;i++){
adj[a[i]].push_back({b[i],t[i]});
adj[b[i]].push_back({a[i],t[i]});
}
for(int i=1;i<=n;i++){
if(vis[i])
continue;
mn={2e9,2e9};
dfs(i,i);
reroot(i,i);
v.push_back(mn);
}
sort(v.begin(),v.end(),greater<pair<int,int>>());
for(int i=1;i<(int)v.size();i++){
adj[v[0].S].push_back({v[i].S,l});
adj[v[i].S].push_back({v[0].S,l});
}
dfs2(1,1);
return mx;
}
#ifdef local
int main(){
freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);
int n,m,l;
cin>>n>>m>>l;
int a[m],b[m],t[m];
for(int i=0;i<m;i++){
cin>>a[i]>>b[i]>>t[i];
}
cout<<travelTime(n,m,l,a,b,t)<<'\n';
}
#else
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
13940 KB |
Output is correct |
2 |
Correct |
34 ms |
14928 KB |
Output is correct |
3 |
Correct |
22 ms |
9860 KB |
Output is correct |
4 |
Correct |
5 ms |
5976 KB |
Output is correct |
5 |
Correct |
5 ms |
5464 KB |
Output is correct |
6 |
Correct |
10 ms |
7004 KB |
Output is correct |
7 |
Incorrect |
1 ms |
4956 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5208 KB |
Output is correct |
2 |
Correct |
1 ms |
4968 KB |
Output is correct |
3 |
Incorrect |
1 ms |
4956 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
13940 KB |
Output is correct |
2 |
Correct |
34 ms |
14928 KB |
Output is correct |
3 |
Correct |
22 ms |
9860 KB |
Output is correct |
4 |
Correct |
5 ms |
5976 KB |
Output is correct |
5 |
Correct |
5 ms |
5464 KB |
Output is correct |
6 |
Correct |
10 ms |
7004 KB |
Output is correct |
7 |
Incorrect |
1 ms |
4956 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
9100 KB |
Output is correct |
2 |
Correct |
20 ms |
9080 KB |
Output is correct |
3 |
Correct |
19 ms |
8848 KB |
Output is correct |
4 |
Correct |
22 ms |
8984 KB |
Output is correct |
5 |
Correct |
23 ms |
9356 KB |
Output is correct |
6 |
Correct |
21 ms |
9944 KB |
Output is correct |
7 |
Correct |
21 ms |
9048 KB |
Output is correct |
8 |
Correct |
19 ms |
8980 KB |
Output is correct |
9 |
Correct |
19 ms |
9004 KB |
Output is correct |
10 |
Correct |
25 ms |
9456 KB |
Output is correct |
11 |
Correct |
1 ms |
4956 KB |
Output is correct |
12 |
Correct |
11 ms |
9768 KB |
Output is correct |
13 |
Correct |
11 ms |
9680 KB |
Output is correct |
14 |
Correct |
11 ms |
9676 KB |
Output is correct |
15 |
Correct |
11 ms |
9676 KB |
Output is correct |
16 |
Correct |
10 ms |
9680 KB |
Output is correct |
17 |
Correct |
10 ms |
9756 KB |
Output is correct |
18 |
Correct |
17 ms |
9680 KB |
Output is correct |
19 |
Correct |
11 ms |
9680 KB |
Output is correct |
20 |
Incorrect |
1 ms |
4952 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5208 KB |
Output is correct |
2 |
Correct |
1 ms |
4968 KB |
Output is correct |
3 |
Incorrect |
1 ms |
4956 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
13940 KB |
Output is correct |
2 |
Correct |
34 ms |
14928 KB |
Output is correct |
3 |
Correct |
22 ms |
9860 KB |
Output is correct |
4 |
Correct |
5 ms |
5976 KB |
Output is correct |
5 |
Correct |
5 ms |
5464 KB |
Output is correct |
6 |
Correct |
10 ms |
7004 KB |
Output is correct |
7 |
Incorrect |
1 ms |
4956 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |