#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> adj[100100];
bitset<100100> vis,vis2;
int mxd[100100], MX, MN;
vector<int> lens;
void dfs1(int n){
vis[n]=1;
for(auto [i,j]:adj[n])if(!vis[i])
dfs1(i), mxd[n]=max(mxd[n],mxd[i]+j);
}
void dfs2(int n,int fromp){
vis2[n]=1,MX=max(MX,fromp);
MN=min(MN,max(fromp,mxd[n]));
vector<int>pre,suf;
for(auto[i,j]:adj[n])if(!vis2[i])
pre.push_back(mxd[i]+j),
suf.push_back(mxd[i]+j);
pre.insert(pre.begin(),0);
suf.push_back(0);
for(int i=1;i<pre.size();i++)
pre[i]=max(pre[i],pre[i-1]);
for(int j=pre.size()-1;j--;)
suf[j]=max(suf[j],suf[j+1]);
int CC=0;
for(auto[i,j]:adj[n])if(!vis2[i]) CC++,
dfs2(i,max({fromp,pre[CC-1],suf[CC+1]})+j);
}
void solve(int n){
for(int i=0;i<n;i++)
if(!vis[i]) MN=1e9,dfs1(i),
dfs2(i,0),lens.push_back(MN);
}
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]});
solve(N);
sort(lens.rbegin(),lens.rend());
if(lens.size()==1)
return MX;
else if(lens.size()==2)
return max(MX,lens[0]+lens[1]+L);
else return max(MX,lens[1]+L+max(lens[0],lens[2]+L));
}
Compilation message
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=1;i<pre.size();i++)
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
20112 KB |
Output is correct |
2 |
Correct |
41 ms |
19272 KB |
Output is correct |
3 |
Correct |
31 ms |
18368 KB |
Output is correct |
4 |
Correct |
7 ms |
5212 KB |
Output is correct |
5 |
Correct |
6 ms |
3932 KB |
Output is correct |
6 |
Correct |
11 ms |
6488 KB |
Output is correct |
7 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
2 ms |
2652 KB |
Output is correct |
3 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
20112 KB |
Output is correct |
2 |
Correct |
41 ms |
19272 KB |
Output is correct |
3 |
Correct |
31 ms |
18368 KB |
Output is correct |
4 |
Correct |
7 ms |
5212 KB |
Output is correct |
5 |
Correct |
6 ms |
3932 KB |
Output is correct |
6 |
Correct |
11 ms |
6488 KB |
Output is correct |
7 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
6108 KB |
Output is correct |
2 |
Correct |
19 ms |
6108 KB |
Output is correct |
3 |
Correct |
23 ms |
6108 KB |
Output is correct |
4 |
Correct |
19 ms |
6108 KB |
Output is correct |
5 |
Correct |
19 ms |
6108 KB |
Output is correct |
6 |
Correct |
19 ms |
6624 KB |
Output is correct |
7 |
Correct |
18 ms |
6360 KB |
Output is correct |
8 |
Correct |
17 ms |
6112 KB |
Output is correct |
9 |
Correct |
20 ms |
6044 KB |
Output is correct |
10 |
Correct |
23 ms |
6356 KB |
Output is correct |
11 |
Correct |
2 ms |
2652 KB |
Output is correct |
12 |
Correct |
6 ms |
3544 KB |
Output is correct |
13 |
Correct |
7 ms |
3544 KB |
Output is correct |
14 |
Correct |
8 ms |
3544 KB |
Output is correct |
15 |
Correct |
8 ms |
3540 KB |
Output is correct |
16 |
Correct |
11 ms |
3540 KB |
Output is correct |
17 |
Correct |
7 ms |
3544 KB |
Output is correct |
18 |
Correct |
7 ms |
3800 KB |
Output is correct |
19 |
Correct |
6 ms |
3544 KB |
Output is correct |
20 |
Correct |
2 ms |
2652 KB |
Output is correct |
21 |
Correct |
1 ms |
2652 KB |
Output is correct |
22 |
Correct |
1 ms |
2860 KB |
Output is correct |
23 |
Correct |
7 ms |
3544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
2 ms |
2652 KB |
Output is correct |
3 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
20112 KB |
Output is correct |
2 |
Correct |
41 ms |
19272 KB |
Output is correct |
3 |
Correct |
31 ms |
18368 KB |
Output is correct |
4 |
Correct |
7 ms |
5212 KB |
Output is correct |
5 |
Correct |
6 ms |
3932 KB |
Output is correct |
6 |
Correct |
11 ms |
6488 KB |
Output is correct |
7 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |