This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include"dreaming.h".
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#define maxn 2000005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cerr<<"passed"<<endl;
#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")
using namespace std;
/**std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;
double timePassed()
{
using namespace std::chrono;
currT = high_resolution_clock::now();
double time = duration_cast<duration<double>>(currT - startT).count();
return time * TIME_MULT;
}*/
typedef pair <int , int> pii;
vector <pii> v[maxn];
bool used[maxn];
pii dfs(int node , int _par , int depth)
{
int current = 0 , cur_ans = depth;
pii _try;
for(pii nb : v[node])
{
if(nb.X == _par)
continue;
_try = dfs(nb.X , node , depth + nb.Y);
if(_try.X + nb.Y > current)
{
current = _try.X + nb.Y;
cur_ans = min(_try.Y , max(depth , current));
}
}
return make_pair(current , cur_ans);
}
pii f(int node , int _par)
{
used[node] = true;
pii current;
current.X = 0;
current.Y = node;
pii current2;
for(pii nb : v[node])
{
if(nb.X == _par)
continue;
current2 = f(nb.X , node);
current2.X += nb.Y;
current = max(current , current2);
}
return current;
}
int travelTime(int N , int M , int L , int A[] , int B[] , int T[])
{
int ans = 0;
for(int i = 0; i < M; i++)
{
v[A[i]].push_back({B[i] , T[i]});
v[B[i]].push_back({A[i] , T[i]});
}
vector <int> distances;
for(int i = 0; i < N; i++)
{
if(used[i] == true)
continue;
int dist = f(i , -1).Y;
pii cur_ans = dfs(dist , -1 , 0);
ans = max(ans , cur_ans.X);
distances.pb(cur_ans.Y);
}
sort(distances.begin() , distances.end());
reverse(distances.begin() , distances.end());
if(distances.size() > 1)
ans = max(ans , distances[0] + distances[1] + L);
if(distances.size() > 2)
ans = max(ans , distances[1] + distances[2] + (2 * L));
return ans;
}
/**int main()
{
#ifdef ONLINE_JUDGE /// promeni
freopen("taxi.in", "r", stdin);
freopen("taxi.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//startT = std::chrono::high_resolution_clock::now();
read();
solve();
return 0;
}*/
Compilation message (stderr)
dreaming.cpp:9:21: warning: extra tokens at end of #include directive
9 | #include"dreaming.h".
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |