#include "dreaming.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
int N, M, L;
int *A, *B, *T;
vim V[100010], C[100010];
vector<pii> D1[100010];
vim D2[100010];
int chk[100010];
vim ar;
int mx;
int dfs1(int now, int par, int dep) {
chk[now]=1;
for (int i=0; i<V[now].size(); i++) {
if (chk[V[now][i]]) continue;
D1[now].push_back({dfs1(V[now][i], now, dep+C[now][i])-dep, V[now][i]});
}
int ret=dep;
for (int i=1; i<D1[now].size(); i++) ret=max(ret, D1[now][i].fi+dep);
return ret;
}
int dfs2(int now, int dep) {
if (!D1[now].size()) return 0;
mx=max(mx, dep+D1[now][0].fi);
if (D1[now].size()>1) mx=max(mx, D1[now][0].fi+D1[now][1].fi);
chk[now]=1;
int ret=max(dep, D1[now][0].fi);
for (int i=0; i<V[now].size(); i++) {
if (chk[V[now][i]]) continue;
ret=min(ret, dfs2(V[now][i], max(dep, (D1[now][0].se==V[now][i]?(D1[now].size()>1?D1[now][1].fi:0):D1[now][0].fi))+C[now][i]));
}
return ret;
}
int travelTime(int N_, int M_, int L_, int A_[], int B_[], int T_[]) {
N=N_; M=M_; L=L_; A=A_; B=B_; T=T_;
for (int i=0; i<M; i++) {
V[A[i]+1].push_back(B[i]+1);
V[B[i]+1].push_back(A[i]+1);
C[A[i]+1].push_back(T[i]);
C[B[i]+1].push_back(T[i]);
}
for (int i=1; i<=N; i++) if (!chk[i]) {dfs1(i, 0, 0);}
for (int i=1; i<=N; i++) sort(all(D1[i]), [](pii x1, pii x2){return x1.fi>x2.fi;});
for (int i=1; i<=N; i++) chk[i]=0;
for (int i=1; i<=N; i++) if (!chk[i]) {ar.push_back(dfs2(i, 0));}
sort(all(ar), [](int x1, int x2){return x1>x2;});
if (ar.size()==1) return mx;
else return max(mx, ar[0]+ar[1]+L);
}
Compilation message
dreaming.cpp: In function 'int dfs1(int, int, int)':
dreaming.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<V[now].size(); i++) {
~^~~~~~~~~~~~~~
dreaming.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1; i<D1[now].size(); i++) ret=max(ret, D1[now][i].fi+dep);
~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int dfs2(int, int)':
dreaming.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<V[now].size(); i++) {
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
24440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
24440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
24440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
16000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
24440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
24440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
