This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include"dreaming.h"
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 79, inf = 1e9 + 79;
vector<int> vis(maxn, 0), dp(maxn, 0);
vector<vector<pair<int, int> > > g(maxn);
void dfs1(int u, int p)
{
vis[u] = 1;
for (int i = 0; i < g[u].size(); i++) if (g[u][i].first == p) { g[u].erase(g[u].begin() + i); break; }
for (pair<int, int> i : g[u])
{
dfs1(i.first, u);
dp[u] = max(dp[u], dp[i.first] + i.second);
}
}
void dfs2(int u, int dist, int &mini, int &dia)
{
mini = min(mini, max(dist, dp[u]));
vector<int> pf(g[u].size() + 1, 0), sf(g[u].size() + 1, 0);
pair<int, int> p(0, 0);
for (int i = 0; i < g[u].size(); i++)
{
int di = dp[g[u][i].first] + g[u][i].second; pf[i + 1] = max(pf[i], di);
if (di > p.first) swap(p.first, p.second), p.first = di;
else if (di > p.second) p.second = di;
}
dia = max({ dia, p.first + p.second, dp[u] + dist });
for (int i = g[u].size() - 1; i >= 0; i--)
sf[i] = max(sf[i + 1], dp[g[u][i].first] + g[u][i].second);
for (int i = 0; i < g[u].size(); i++)
dfs2(g[u][i].first, max({ dist, pf[i], sf[i + 1] }) + g[u][i].second, mini, dia);
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
for (int i = 0; i < m; i++)
g[a[i]].push_back({ b[i], t[i] }), g[b[i]].push_back({ a[i], t[i] });
vector<int> v; int ans = 0;
for (int i = 0; i < n; i++)
if (!vis[i])
{
v.push_back(inf);
dfs1(i, -1), dfs2(i, 0, v.back(), ans);
}
return max(v[0] + l + v[1], ans);
}
Compilation message (stderr)
dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i = 0; i < g[u].size(); i++) if (g[u][i].first == p) { g[u].erase(g[u].begin() + i); break; }
| ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, int&, int&)':
dreaming.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i = 0; i < g[u].size(); i++)
| ~~^~~~~~~~~~~~~
dreaming.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i = 0; i < g[u].size(); i++)
| ~~^~~~~~~~~~~~~
# | 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... |