#include<bits/stdc++.h>
#define endl '\n'
#include"dreaming.h"
using namespace std;
struct cell
{
int to,cost;
};
int n,m,l,a[200005],b[200005],t[200005],used[200005],lead[200005],dp[200005],sdp[200005],mid,mind1,mind2,mind3,sma;
vector<cell>v[200005];
void read()
{
cin>>n>>m>>l;
for(int i=0;i<m;i++)
{
cin>>a[i]>>b[i]>>t[i];
}
}
void make_dp(int beg)
{
used[beg]=1;
cell w;
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(!used[w.to])
{
make_dp(w.to);
if(dp[beg]<dp[w.to]+w.cost)
{
sdp[beg]=dp[beg];
dp[beg]=dp[w.to]+w.cost;
}
else sdp[beg]=max(sdp[beg],dp[w.to]+w.cost);
}
}
sma=max(sma,dp[beg]+sdp[beg]);
}
void find_mid(int beg,int izm)
{
used[beg]=1;
cell w;
int ma=0,sma=0;
cell ind;
ind.cost=0;
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(!used[w.to]&&dp[w.to]>ma)
{
ma=dp[w.to];
ind=w;
}
}
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(!used[w.to]&&w.to!=ind.to&&dp[w.to]+w.cost>sma)
{
sma=dp[w.to]+w.cost;
}
}
izm=max(izm,sma)+ind.cost;
if(dp[beg]<=max(izm,ma))
{
mid=beg;
}
else
{
find_mid(w.to,izm);
}
}
void make_lead(int beg,int le)
{
used[beg]=2;
lead[beg]=le;
cell w;
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(used[w.to]<2)
{
make_lead(w.to,le);
}
}
}
void find_max_lead()
{
int ma=-1,ind=-1;
for(int i=0;i<n;i++)
{
if(ma<dp[lead[i]])
{
ma=dp[lead[i]];
ind=lead[i];
}
}
mind1=ind;
ind=-1;
ma=-1;
for(int i=0;i<n;i++)
{
if(lead[i]!=mind1&&ma<dp[lead[i]])
{
ma=dp[lead[i]];
ind=lead[i];
}
}
mind2=ind;
ind=-1;
ma=-1;
for(int i=0;i<n;i++)
{
if(lead[i]!=mind1&&lead[i]!=mind2&&ma<dp[lead[i]])
{
ma=dp[lead[i]];
ind=lead[i];
}
}
mind3=ind;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
n=N;
m=M;
l=L;
for(int i=0;i<m;i++)
{
a[i]=A[i];
b[i]=B[i];
t[i]=T[i];
cell g;
g.to=b[i];
g.cost=t[i];
v[a[i]].push_back(g);
g.to=a[i];
v[b[i]].push_back(g);
}
for(int i=0;i<n;i++)
{
if(!used[i])make_dp(i);
}
memset(used,0,sizeof(used));
for(int i=0;i<n;i++)
{
if(!used[i])
{
find_mid(i,0);
make_lead(i,mid);
mid=0;
}
}
memset(used,0,sizeof(used));
memset(dp,0,sizeof(dp));
memset(sdp,0,sizeof(sdp));
for(int i=0;i<n;i++)
{
if(!used[lead[i]])make_dp(lead[i]);
}
find_max_lead();
if(mind2==-1)return sma;
if(mind3==-1)return max(sma,dp[mind1]+dp[mind2]+l);
//return max(max(sma,dp[mind1]+dp[mind2]+l),dp[mind2]+dp[mind3]+2*l);
}
/*int main()
{
read();
cout<<travelTime(n,m,l,a,b,t)<<endl;
return 0;
}
*/
Compilation message
dreaming.cpp: In function 'void make_dp(int)':
dreaming.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i=0;i<v[beg].size();i++)
| ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void find_mid(int, int)':
dreaming.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0;i<v[beg].size();i++)
| ~^~~~~~~~~~~~~~
dreaming.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=0;i<v[beg].size();i++)
| ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void make_lead(int, int)':
dreaming.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i=0;i<v[beg].size();i++)
| ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:164:1: warning: control reaches end of non-void function [-Wreturn-type]
164 | }
| ^
dreaming.cpp: In function 'void find_mid(int, int)':
dreaming.cpp:64:14: warning: 'w.cell::to' may be used uninitialized in this function [-Wmaybe-uninitialized]
64 | if(dp[beg]<=max(izm,ma))
| ~~~~~~^
dreaming.cpp:58:23: warning: 'ind.cell::to' may be used uninitialized in this function [-Wmaybe-uninitialized]
58 | if(!used[w.to]&&w.to!=ind.to&&dp[w.to]+w.cost>sma)
| ~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
18000 KB |
Output is correct |
| 2 |
Correct |
42 ms |
17652 KB |
Output is correct |
| 3 |
Correct |
25 ms |
15840 KB |
Output is correct |
| 4 |
Correct |
8 ms |
9052 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8288 KB |
Output is correct |
| 6 |
Correct |
12 ms |
9820 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
7448 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7516 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7516 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
7516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
18000 KB |
Output is correct |
| 2 |
Correct |
42 ms |
17652 KB |
Output is correct |
| 3 |
Correct |
25 ms |
15840 KB |
Output is correct |
| 4 |
Correct |
8 ms |
9052 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8288 KB |
Output is correct |
| 6 |
Correct |
12 ms |
9820 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
7448 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
10848 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7516 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7516 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
7516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
18000 KB |
Output is correct |
| 2 |
Correct |
42 ms |
17652 KB |
Output is correct |
| 3 |
Correct |
25 ms |
15840 KB |
Output is correct |
| 4 |
Correct |
8 ms |
9052 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8288 KB |
Output is correct |
| 6 |
Correct |
12 ms |
9820 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
7448 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
