#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fi first
#define se second
const int sim=100000;
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];
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());
if(sem[x].size()==0) return 0;
else return sem[x][0].fi;
}
long long cari2(int x,long long baw){
if(sem[x].size()==0) return 1e18;
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]));
for(int i=0; i<sem[x].size(); i++){
if(sem[x][i].fi==pen){
maxi=min(maxi,cari2(sem[x][i].se.fi,baw+sem[x][i].se.se));
}
}
return maxi;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
memset(dp,-1,sizeof dp);
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);
}
vector<long long> jaw;
for(int i=0; i<v.size(); i++){
cari(v[i],-1);
long long baw=0;
if(sem[v[i]].size()>1){
baw=sem[v[i]][1].fi;
}
jaw.push_back(cari2(v[i],baw));
}
sort(jaw.begin(),jaw.end());
long long has=jaw[0];
if(jaw.size()>=2){
has=max(has,jaw[1]+jaw[0]+l);
}
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:23: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:40: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:68:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1099 ms |
27504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1099 ms |
27504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1099 ms |
27504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
11760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1099 ms |
27504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1099 ms |
27504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
