#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define designed ios_base::sync_with_stdio(0);
#define by cin.tie(0);
#define AndreasK cout.tie(0);
//#define int long long
#define ii pair <int,int>
#define vi vector <int>
#define iii pair <int,ii>
#define vii vector <ii>
#define vc vector <char>
#define vb vector <bool>
vector <vii> g;
map <int,int> m;
vi v;
map <int,int> mn;
void dfs(int curr,int prev,int dist,int st){
v[curr]=st;
m[st]=max(m[st],dist);
for (auto nxt:g[curr]){
if (nxt.first!=prev)
dfs(nxt.first,curr,nxt.second+dist,st);
}
}
void dfs2(int curr,int prev,int dist,int st){
v[curr]=st;
mn[st]=min(mn[st],max(m[st]-dist,dist));
for (auto nxt:g[curr]){
if (nxt.first!=prev)
dfs2(nxt.first,curr,nxt.second+dist,st);
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
g.assign(N,vii());
for (int c=0;c<M;c++){
g[A[c]].push_back({B[c],T[c]});
g[B[c]].push_back({A[c],T[c]});
}
m.clear();
int st=0;
v.assign(N,0);
for (int c=0;c<N;c++){
if (v[c]==0){
st++;
dfs(c,c,0,st);
}
}
mn.clear();
mn[1]=m[1];
mn[2]=m[2];
st=0;
v.assign(N,0);
for (int c=0;c<N;c++){
if (v[c]==0){
st++;
dfs2(c,c,0,st);
}
}
return mn[1]+mn[2]+L;
}
/*int32_t main(){
designed by AndreasK
freopen("akinput.txt","r",stdin);
int N,M,L;
cin>>N>>M>>L;
int A[M],B[M],T[M];
for (int c=0;c<M;c++)
cin>>A[c];
for (int c=0;c<M;c++)
cin>>B[c];
for (int c=0;c<M;c++)
cin>>T[c];
cout<<travelTime(N,M,L,A,B,T);
return 0;}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
30 ms |
13392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
30 ms |
13392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
48 ms |
11604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
30 ms |
13392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |