#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fi first
#define se second
const int sim=100010;
int p[sim];
bool udah[sim];
vector<pair<int,int> > adj[sim];
long long dp[sim];
vector<pair<long long,pair<int,int> > >sem[sim];
long long mjaw,mind;
int par(int x){
if(p[x]==x) return x;
else return p[x]=par(p[x]);
}
long long cari(int x, int seb){
for(int i=0; i<adj[x].size(); i++){
int ind=adj[x][i].fi;
if(ind!=seb){
sem[x].push_back(mp(cari(ind,x)+adj[x][i].se,mp(ind,adj[x][i].se)));
}
}
sort(sem[x].begin(),sem[x].end());
reverse(sem[x].begin(),sem[x].end());
if(sem[x].size()==0) return dp[x]=0;
else return dp[x]=sem[x][0].fi;
}
long long cari2(int x,long long baw){
if(sem[x].size()==0) return baw;
if(sem[x].size()>1)baw=max(baw,sem[x][1].fi);
// long long pen=sem[x][0].fi;
long long maxi=1e18;
maxi=min(maxi,max(baw,dp[x]));
// cout<<"dp "<<x<<' '<<dp[x]<<endl;
for(int i=0; i<sem[x].size(); i++){
long long seu=baw;
if(i==0){
seu=max(seu,sem[x][1].fi);
}else {
seu=max(seu,sem[x][0].fi);
}
maxi=min(maxi,cari2(sem[x][i].se.fi,seu+sem[x][i].se.se));
}
// cout<<x<<' '<<maxi<<endl;
// return maxi;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i=0; i<n; i++){
p[i]=i;
}
for(int i=0; i<m; i++){
adj[a[i]].push_back(mp(b[i],t[i]));
adj[b[i]].push_back(mp(a[i],t[i]));
int x=par(a[i]),y=par(b[i]);
p[x]=y;
}
vector<int> v;
for(int i=0; i<n; i++){
int x=par(i);
if(!udah[x]) v.push_back(x);
udah[x]=1;
}
long long has=0;
vector<long long> jaw;
//cout<<v.size()<<endl;
for(int i=0; i<v.size(); i++){
// cout<<v[i]<<endl;
cari(v[i],-1);
long long baw=0;
// if(sem[v[i]].size()>1){
// baw=sem[v[i]][1].fi;
// }
// mjaw=1e18;
if(sem[v[i]].size()>1){
has=max(has,sem[v[i]][0].fi+sem[v[i]][1].fi);
}else if(sem[v[i]].size()==1){
has=max(has,dp[v[i]]);
}
long long wk=cari2(v[i],baw);
// cout<<wk<<endl<<endl;
jaw.push_back(wk);
}
sort(jaw.begin(),jaw.end());
reverse(jaw.begin(),jaw.end());
// if(jaw.size()<=1){
// for(int i=1; i<=1e9; i++){
// }
// }
if(jaw.size()>=2){
has=max(has,jaw[1]+jaw[0]+l);
// for(int i=1; i<=1e9; i++){
// }
}
if(jaw.size()>=3){
has=max(has,jaw[1]+jaw[2]+l+l);
}
return has;
}
Compilation message
dreaming.cpp: In function 'long long int cari(int, int)':
dreaming.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[x].size(); i++){
~^~~~~~~~~~~~~~
dreaming.cpp: In function 'long long int cari2(int, long long int)':
dreaming.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<sem[x].size(); i++){
~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++){
~^~~~~~~~~
dreaming.cpp: In function 'long long int cari2(int, long long int)':
dreaming.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
24336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
24336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
24336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
10224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
24336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
24336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
