| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1247948 | nekolie | Dreaming (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
// Fluixarata or Cyngulini?
// That is the question...
//#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100001, inf = (1<<30);
int dp[maxn][2], odp;
bool odw[maxn]; vector<pair<int,int>> tree[maxn];
void dfs(int v, int p) {
odw[v] = true;
int x = 0, y = 0;
for (auto [u,w] : tree[v]) {
if (u == p)
continue;
dfs(u,v), dp[v][0] = max(dp[v][0],dp[u][0]+w);
if (dp[u][0]+w > x)
y = x, x = dp[u][0]+w;
else if (dp[u][0]+w > y)
y = dp[u][0]+w;
}
odp = max(odp,x+y);
}
void dfs2(int v, int p, int &maks) {
int opt = -inf; maks = min(maks,max(dp[v][0],dp[v][1]));
for (auto [u,w] : tree[v])
if (u != p)
dp[u][1] = max(dp[v][1],opt)+w, opt = max(opt,dp[u][0]+w);
reverse(tree[v].begin(),tree[v].end()), opt = -inf;
for (auto [u,w] : tree[v])
if (u != p)
dp[u][1] = max(dp[u][1],opt+w), opt = max(opt,dp[u][0]+w), dfs2(u,v,maks);
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
int x = -inf, y = -inf, z = -inf;
for (int i = 0; i < m; i++)
tree[A[i]+1].push_back({B[i]+1,T[i]}), tree[B[i]+1].push_back({A[i]+1,T[i]});
for (int i = 1; i <= n; i++) {
if (odw[i])
continue;
int maks = inf;
dfs(i,0), dfs2(i,0,maks);
if (maks > x)
z = y, y = x, x = maks;
else if (maks > y)
z = y, y = maks;
else if (maks > z)
z = maks;
}
return max({odp,x+y+l,y+z+2*l});
}