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 "race.h"
#include "vector"
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 1e9;
int N, K;
int shift;
int moves_shift;
int ans = INF;
vector<vector<pi>> adj_list;
vector<int> sz;
vector<int> minv;
vector<int> dep;
vector<int> dist;
// Euler tour variables
vector<int> tin;
vector<int> tout;
vector<int> trav;
int counter = 0;
void calculate(int node, int par, bool is_heavy)
{
int BigKid = -1;
int BigW = 0;
int BigV = 0;
for (auto [neigh, w] : adj_list[node]) {
if (neigh != par && sz[neigh] > BigV) {
BigKid = neigh;
BigW = w;
BigV = sz[neigh];
}
}
for (auto [neigh, w] : adj_list[node]) {
if (neigh != par && neigh != BigKid)
calculate(neigh, node, false);
}
if (BigKid != -1) {
calculate(BigKid, node, true);
shift -= BigW;
moves_shift++;
}
if (K + shift >= 0 && K + shift <= 2 * K)
ans = min(ans, minv[K + shift] + moves_shift);
if (shift >= 0 && shift <= 2 * K)
minv[shift] = -moves_shift;
for (auto [neigh, w] : adj_list[node]) {
if (neigh == par || neigh == BigKid)
continue;
for (int t = tin[neigh]; t < tout[neigh]; t++) {
int cur = trav[t];
int len = dist[cur] - dist[node];
int compliment = K - len;
int v = dep[cur] - dep[node];
if (compliment + shift >= 0 && compliment + shift <= 2 * K) {
ans = min(ans, minv[compliment + shift] + moves_shift + v);
}
}
for (int t = tin[neigh]; t < tout[neigh]; t++) {
int cur = trav[t];
int len = dist[cur] - dist[node];
int v = dep[cur] - dep[node];
if (len + shift >= 0 && len + shift <= 2 * K) {
minv[len + shift] = min(minv[len + shift], v - moves_shift);
}
}
}
if (!is_heavy) {
for (int t = tin[node]; t < tout[node]; t++) {
int cur = trav[t];
int len = dist[cur] - dist[node];
if (len + shift >= 0 && len + shift <= 2 * K) {
minv[len + shift] = INF;
}
}
shift = K;
moves_shift = 0;
}
}
void init(int node, int par)
{
tin[node] = counter++;
trav[tin[node]] = node;
sz[node] = 1;
for (auto [neigh, w] : adj_list[node]) {
if (neigh == par)
continue;
dep[neigh] = dep[node] + 1;
dist[neigh] = dist[node] + w;
init(neigh, node);
sz[node] += sz[neigh];
}
tout[node] = counter;
}
int best_path(int n, int k, int H[][2], int L[])
{
N = n;
K = k;
adj_list.resize(N);
sz.resize(N);
minv.assign(2 * K + 1, INF);
dep.resize(N);
dist.resize(N);
shift = K;
tin.resize(N);
tout.resize(N);
trav.resize(N);
for (int i = 0; i < N - 1; i++) {
int u = H[i][0];
int v = H[i][1];
int w = L[i];
adj_list[u].pb(mp(v, w));
adj_list[v].pb(mp(u, w));
}
init(0, -1);
calculate(0, -1, true);
if (ans == INF)
return -1;
else
return ans;
}
Compilation message (stderr)
race.cpp: In function 'void calculate(int, int, bool)':
race.cpp:35:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
35 | for (auto [neigh, w] : adj_list[node]) {
| ^
race.cpp:43:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
43 | for (auto [neigh, w] : adj_list[node]) {
| ^
race.cpp:57:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
57 | for (auto [neigh, w] : adj_list[node]) {
| ^
race.cpp: In function 'void init(int, int)':
race.cpp:102:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
102 | for (auto [neigh, w] : adj_list[node]) {
| ^
# | 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... |