#include "dreaming.h"
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back
#define ss second
#define ff first
#define ext exit(0)
using namespace std;
int i,m[100001],par[100001],dep[100001],u1,u2,lc;
vector<pair<int,int> >v[100001];
bool boo[100001];
queue<ll>q;
vector<ll> vc;
ll fnd(int v1,int v2){
if(dep[v1]<dep[v2]) swap(v1,v2);
while(dep[v1]>dep[v2]){
v1=par[v1];
}
if(v1==v2) return v1;
while(v1!=v2){
v1=par[v1];
v2=par[v2];
}
return v1;
}
ll dia(int k){
bool baa[100001];
dep[k]=0;
memset(baa,0,sizeof baa);
baa[k]=1;
par[k]=-1;
q.push(k);
boo[k]=1;
ll idx,s=0;
while(!q.empty()){
int kk=q.front();
if(m[kk]>=s){
s=m[kk];
idx=kk;
}
for(int j=0;j<v[kk].size();j++){
if(baa[v[kk][j].ff]) continue;
boo[v[kk][j].ff]=1;
baa[v[kk][j].ff]=1;
m[v[kk][j].ff]=m[kk]+v[kk][j].ss;
par[v[kk][j].ff]=kk;
dep[v[kk][j].ff]=dep[kk]+1;
q.push(v[kk][j].ff);
}
q.pop();
}
return idx;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(i=0;i<M;i++){
v[A[i]].pub(mp(B[i],T[i]));
v[B[i]].pub(mp(A[i],T[i]));
}
for(i=0;i<N;i++){
if(boo[i]) continue;
u1=dia(i);
u2=dia(u1);
lc=fnd(u1,u2);
ll s=m[u1]+m[u2]-2*m[lc],s1=0,lol=1e9,sos=0;
while(u1!=lc){
if(abs(s1-s)<lol){
lol=abs(s1-s);
sos=max(s1,s);
}
s1+=m[u1]-m[par[u1]];
s-=m[u1]-m[par[u1]];
u1=par[u1];
}
s=m[u1]+m[u2]-2*m[lc],s1=0,lol=1e9;
while(u2!=lc){
if(abs(s1-s)<lol){
lol=abs(s1-s);
sos=max(s1,s);
}
s1+=m[u2]-m[par[u2]];
s-=m[u2]-m[par[u2]];
u2=par[u2];
}
vc.pub(sos);
}
sort(vc.begin(),vc.end());
for(i=0;i<vc.size();i++){
cout<<vc[i]<<" ";
}
cout<<"\n";
if(vc.size()>=3){
return max(vc.back()+vc[vc.size()-2]+L,vc[vc.size()-2]+vc[vc.size()-3]+2*L);
}
else {
return vc.back()+vc[vc.size()-2]+L;
}
}
Compilation message
dreaming.cpp: In function 'long long int dia(int)':
dreaming.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v[kk].size();j++){
~^~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:90:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<vc.size();i++){
~^~~~~~~~~~
dreaming.cpp: In function 'long long int dia(int)':
dreaming.cpp:55:9: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
return idx;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
7928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
7928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
7928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
572 ms |
7052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
7928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
7928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
