#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a));
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
int dist[100005], deg[100005], dp[100005], dpup[100005], dpdown[100005], n, m, l, diameter, ans, maxchild, secondmax;
vp edges[100005];
vi v, comp;
bool vis[100005];
void dfs(int x, int p) {
diameter = max(diameter, dist[x]);
vis[x] = true;
v.pb(x);
for (auto edge: edges[x]) {
if (edge.fi != p) {
dist[edge.fi] = dist[x] + edge.se;
dfs(edge.fi, x);
}
}
}
int find_diameter(int root) {
dist[root] = 0;
diameter = 0;
v.clear();
dfs(root, -1);
return diameter;
}
//compute initial dp and dpdown
int dfs2(int x, int p) {
int maxx = 0;
if (p == -1) {
for (auto edge: edges[x]) {
int child = dfs2(edge.fi, x) + edge.se;
if (child > maxx) {
maxx = child;
maxchild = edge.fi;
} else {
secondmax = max(secondmax, child);
}
}
dpdown[x] = maxx;
dp[x] = maxx;
return dpdown[x];
}
for (auto edge: edges[x]) {
if (edge.fi != p) {
int child = dfs2(edge.fi, x) + edge.se;
maxx = max(maxx, child);
}
}
dpdown[x] = maxx;
dp[x] = maxx;
return dpdown[x];
}
//update dp and dpup
void dfs3(int x, int p) {
if (p == -1) {
for (auto edge: edges[x]) {
if (edge.fi == maxchild) {
dpup[edge.fi] = secondmax + edge.se;
} else {
dpup[edge.fi] = dpdown[x] + edge.se;
}
dp[edge.fi] = max(dpup[edge.fi], dpdown[edge.fi]);
dfs3(edge.fi, x);
}
return;
}
dp[x] = max(dp[x], dpup[x]);
for (auto edge: edges[x]) {
if (edge.fi != p) {
dpup[edge.fi] = max(dpup[edge.fi], dpup[x] + edge.se);
dp[edge.fi] = max(dpup[edge.fi], dpdown[edge.fi]);
dfs3(edge.fi, x);
}
}
}
void find_shortest_path() {
int useless = dfs2(v[0], -1);
dfs3(v[0], -1);
int tmp = inf * 2;
for (int node: v) {
tmp = min(tmp, dp[node]);
cout << node << ' ' << dpup[node] << ' ' << dpdown[node] << ' ' << dp[node] << endl;
}
comp.pb(tmp);
//cout << "tmp " << tmp << endl;
}
int travelTime(int N, int M, int L, int u[], int v[], int t[]) {
n = N;
m = M;
l = L;
FOR(i, 0, m-1) {
edges[u[i] + 1].emplace_back(v[i] + 1, t[i]);
edges[v[i] + 1].emplace_back(u[i] + 1, t[i]);
deg[u[i] + 1]++;
deg[v[i] + 1]++;
}
FOR(i, 1, n) {
if (!vis[i]) {
ans = max(ans, find_diameter(i));
find_shortest_path();
}
}
int sz = comp.size();
sort(all(comp));
reverse(all(comp));
if (sz == 1) {}
else if (sz == 2) {
ans = max(ans, L + comp[0] + comp[1]);
} else {
ans = max(ans, L + comp[0] + comp[1]);
ans = max(ans, L + L + comp[1] + comp[2]);
}
return ans;
}
Compilation message
dreaming.cpp: In function 'void find_shortest_path()':
dreaming.cpp:98:7: warning: unused variable 'useless' [-Wunused-variable]
98 | int useless = dfs2(v[0], -1);
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
310 ms |
16628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
310 ms |
16628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
310 ms |
16628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
278 ms |
8820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
310 ms |
16628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
310 ms |
16628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
