#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
long long ww,lv[300005],lv1[300005],mx,vert,fix[300005],x1,x2,x,y;
std::vector <long long> v[300005],vv,ans;
map < pair <long long, long long > , long long > mp;
void dfs(int a, int p)
{
fix[a]=1;
if (ww==1) vv.push_back(a);
if (p!=-1)
lv[a]=lv[p]+mp[{a,p}];
else lv[a]=0;
if (lv[a]>mx)
{
vert=a;
mx=lv[a];
}
for (int i=0; i<v[a].size(); i++)
{
if (v[a][i]!=p)
{
dfs(v[a][i],a);
}
}
}
void dfs1(int a, int p)
{
if (p!=-1)
lv1[a]=lv1[p]+mp[{a,p}];
else lv1[a]=0;
for (int i=0; i<v[a].size(); i++)
{
if (v[a][i]!=p)
{
dfs1(v[a][i],a);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
/*cin>>N>>M>>L;
for (int i=0; i<M; i++)
{
cin>>A[i];
}
for (int i=0; i<M; i++)
{
cin>>B[i];
}
for (int i=0; i<M; i++)
{
cin>>T[i];
}*/
for (int i=0; i<M; i++)
{
mp[{A[i],B[i]}]=T[i];
mp[{B[i],A[i]}]=T[i];
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
}
for (int i=0; i<N; i++)
{
mx=0;
if (!fix[i])
{
//cout<<i<<" s"<<endl;
vv.clear();
// cout<<i<<endl<<endl;
ww=1;
dfs(i,-1);
x1=vert;
// cout<<lv[9]<<" "<<lv[3]<<" "<<lv[5]<<" "<<lv[11]<<endl;
ww=0;
mx=0;
dfs(x1,-1);
// cout<<x1<<" h "<<lv[0]<<endl;
x2=vert;
dfs1(x2,-1);
//cout<<lv[8]<<" "<<lv1[8]<<endl;
x=1e9;
// cout<<x1<<" s "<<x2<<endl;
for (int j=0; j<vv.size(); j++)
{
// cout<<vv[j]<<" "<<lv[vv[j]]<<" "<<lv1[vv[j]]<<endl;
y=max(lv[vv[j]], lv1[vv[j]]);
x=min(x, y);
}
ans.push_back(x);
cout<<x<<endl;
}
}
sort(ans.begin(), ans.end());
reverse(ans.begin(), ans.end());
cout<<endl;
if (ans.size()>=3)
{
return max(ans[1]+ans[2]+2*L, ans[0]+ans[1]+L);
}
if (ans.size()>=2)
{
return ans[0]+ans[1]+L;
}
return 0;
}
Compilation message
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for (int i=0; i<v[a].size(); i++)
| ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i=0; i<v[a].size(); i++)
| ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:87:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int j=0; j<vv.size(); j++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
397 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
397 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
397 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
325 ms |
17076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
397 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
397 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
