#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define P push
#define I insert
typedef long long ll;
const ll INF=1000000000000000;
const int maxn=100000;
int n,m,l;
vector<pair<int,ll> > v[maxn];
vector<int> rts;
int parent[maxn];
ll maxsublen[maxn];
ll maxlen[maxn];
int gr[maxn];
ll dfs(int x,int z){
for(int i=0;i<v[x].size();i++){
int y=v[x][i].F;
if(parent[x]==y)continue;
parent[y]=x;
gr[y]=z;
maxsublen[x]=max(maxsublen[x],dfs(y,z)+v[x][i].S);
}
return maxsublen[x];
}
void dfs1(int x,ll maxpar){
vector<pair<ll,int> > subs;
for(int i=0;i<v[x].size();i++){
int y=v[x][i].F;
if(parent[x]==y)continue;
subs.PB(MP(maxsublen[y]+v[x][i].S,y));
}
sort(subs.rbegin(),subs.rend());
for(int i=0;i<v[x].size();i++){
int y=v[x][i].F;
if(parent[x]==y)continue;
ll nmaxpar;
if(subs[0].S==y && subs.size()>1)nmaxpar=max(maxpar,subs[1].F);
else nmaxpar=max(maxpar,subs[0].F);
nmaxpar+=v[x][i].S;
maxlen[y]=max(maxsublen[y],nmaxpar);
dfs1(y,nmaxpar);
}
return;
}
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++){
v[A[i]].PB(MP(B[i],(ll)T[i]));
v[B[i]].PB(MP(A[i],(ll)T[i]));
}
memset(parent,-1,sizeof(parent));
memset(maxsublen,0,sizeof(maxsublen));
for(int i=0;i<n;i++){
if(parent[i]!=-1)continue;
parent[i]=i;
rts.PB(i);
gr[i]=rts.size()-1;
dfs(i,rts.size()-1);
maxlen[i]=maxsublen[i];
dfs1(i,0);
}
ll grmin[rts.size()];
for(int i=0;i<rts.size();i++)grmin[i]=INF;
for(int i=0;i<n;i++){
grmin[gr[i]]=min(grmin[gr[i]],maxlen[i]);
}
sort(grmin,grmin+rts.size());
ll ans=INF;
if(rts.size()==1)ans=grmin[0];
else if(rts.size()==2)ans=grmin[0]+grmin[1]+l;
else {
ans=min(grmin[0]+grmin[1]+l,grmin[1]+grmin[2]+2*l);
}
return ans;
}
Compilation message
dreaming.cpp: In function 'll dfs(int, int)':
dreaming.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs1(int, ll)':
dreaming.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
dreaming.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i=0;i<rts.size();i++)grmin[i]=INF;
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
20940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
20940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
8524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
20940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
