#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100000];
vector<int> adjw[100000];
int sub[100000];
bool v[100000];
int dfs1(int now, int from){
v[now] = true;
sub[now] = 0;
for(int i = 0; i<adj[now].size(); i++){
int to = adj[now][i];
if(to==from){
continue;
}
sub[now] = max(sub[now],adjw[now][i] + dfs1(to, now));
}
return sub[now];
}
int dfs2(int now, int from, int above){
int ret = 1000000007;
vector<pair<int, int> > li;
//deep, loc
for(int i = 0; i<adj[now].size(); i++){
int to = adj[now][i];
if(to==from){
continue;
}
li.push_back(make_pair(sub[to]+adjw[now][i],i));
}
if(li.size()==0){
return above;
}
int maxi = 0;
for(int i = 1; i<li.size(); i++){
if(li[i].first > li[maxi].first){
maxi = i;
}
}
ret = min(ret, max(above,li[maxi].first));
int ind = li[maxi].second;
for(int i = 0; i<li.size(); i++){
if(i==maxi){
continue;
}
above = max(above,li[i].first);
}
above += adjw[now][ind];
ret = min(ret, dfs2(adj[now][ind],now,above));
return ret;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i = 0; i<m; i++){
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
adjw[a[i]].push_back(t[i]);
adjw[b[i]].push_back(t[i]);
}
vector<int> all;
for(int i = 0; i<n; i++){
if(v[i]){
continue;
}
bool bef[n];
for(int j = 0; j<n; j++){
bef[j] = v[j];
}
bool same[n];
int now = dfs1(i,-1);
for(int j = 0; j<n; j++){
same[j] = !bef[j] && v[j];
if(same[j]){
now = min(now,dfs1(j,-1));
}
}
all.push_back(now);
}
// for(int i = 0; i<n; i++){
// v[i] = false;
// }
// vector<int> all;
// for(int i = 0; i<n; i++){
// if(adj[i].size()==0){
// assert(!v[i]);
// v[i] = true;
// all.push_back(0);
// }
// if(v[i]){
// continue;
// }
// dfs1(i,-1);
// all.push_back(dfs2(i,-1,0));
// }
// for(int i = 0; i<n; i++){
// assert(v[i]);
// }
sort(all.begin(),all.end());
int ans = 0;
if(all.size()>0){
ans = max(ans,all[all.size()-1]);
}
if(all.size()>1){
ans = max(ans,all[all.size()-1] + all[all.size()-2] + l);
}
if(all.size()>2){
ans = max(ans,all[all.size()-3] + all[all.size()-2] + l + l);
}
return ans;
}
Compilation message
dreaming.cpp: In function 'int dfs1(int, int)':
dreaming.cpp:11:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int dfs2(int, int, int)':
dreaming.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
dreaming.cpp:35:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i<li.size(); i++){
~^~~~~~~~~~
dreaming.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<li.size(); i++){
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
19320 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
19320 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
19320 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1069 ms |
10128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
19320 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
19320 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
