#include "dreaming.h"
#include<bits/stdc++.h>
#define fori(a,b,c) for(int a=b; a<c; a++)
#define ford(a,b,c) for(int a=b; a>=c; a++)
#define pb push_back
#define pq priority_queue
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
vector< pii >v[100004];
vector< int >el[2];
int vis[100004];
int sp[100004];
int lp[2];
int dis[100004];
int deep[100004];
int g[100004];
int dp[2];
int reans[2];
int dfs(int u, int pre, int gr){
int s=v[u].size();
vis[u]=1;
el[gr].pb(u);
int res;
fori(i,0,s){
if(pre!=v[u][i].fi){
res=dfs(v[u][i].fi,u,gr);
dis[u]+=dis[v[u][i].fi]+v[u][i].se;
}
}
deep[u]=deep[pre]+1;
g[u]=gr;
res=max(res,dis[u]);
dp[gr]=max(dp[gr],deep[u]-1);
return res;
}
/*void dfs2(int u, int pre,int gr){
int s=v[u].size();
int loc[100004];
fori(i,0,dp[gr]){
if()
}
fori(i,0,s){
if(pre!=v[u][i].fi){
dfs2(v[u][i],u);
}
}
}*/
int n;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N;
fori(i,0,M){
v[A[i]].pb(mp(B[i],T[i]));
v[B[i]].pb(mp(A[i],T[i]));
}
int gr=0;
fori(i,0,n){
if(v[i].size()==1 && !vis[i]){
int k = dfs(i,i,gr);
int els=el[gr].size();
int ans=dis[el[gr][els-1]];
reans[gr]=i;
fori(j,1,els){
int loc[100004];
int locmax=0;
fori(l,0,els){
if(l==j){
loc[l]=0;
}
if(l>j){
loc[l]=dis[el[gr][l]]-dis[el[gr][j]];
}
if(l<j){
loc[l]=dis[el[gr][j]]-dis[el[gr][l]];
}
locmax=max(locmax,loc[l]);
}
ans=min(locmax,ans);
reans[gr]=el[gr][j];
lp[gr]=ans;
}
gr++;
}
}
return lp[0]+lp[1]+L;
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:68:8: warning: unused variable 'k' [-Wunused-variable]
int k = dfs(i,i,gr);
^
dreaming.cpp: In function 'int dfs(int, int, int)':
dreaming.cpp:28:6: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
int res;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
14580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
14580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
14580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
9848 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
14580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
14580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
