| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1318218 | AzeTurk810 | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
```
/*
_ __ __ __ ____ ___ _ __
| | /| / / ___ _ / /_ ____ / / / __ \ ___ ___ / _ \ (_) ___ ____ ___ / /
| |/ |/ / / _ `// __// __/ / _ \ / /_/ / / _ \/ -_) / ___/ / / / -_)/ __// -_) /_/
|__/|__/ \_,_/ \__/ \__/ /_//_/ \____/ /_//_/\__/ /_/ /_/ \__/ \__/ \__/ (_)
*/
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
// constants
// functions
int GCD(int A, int B);
int LCM(int A, int B);
int power(int base, int exponent);
// structs
struct graph
{
vector <vector <pair <int, int> > > g;
vector <int> sz, mne;
vector <bool> dead;
int mncnt;
void cleanse()
{
fill(dead.begin(), dead.end(), false);
fill(mne.begin(), mne.end(), INT_MAX);
mncnt = INT_MAX;
mne[0] = 0;
}
void prep(int n, int k)
{
g.resize(n);
sz.resize(n);
dead.resize(n);
mne.resize(k);
cleanse();
}
void adde(int u, int v, int w)
{
g[u].push_back({v, w});
g[v].push_back({u, w});
}
void DFS(int v, int P)
{
sz[v] = 1;
for (auto [u, w] : g[v])
{
if (dead[u] || u == P)
{
continue;
}
DFS(u, v);
sz[v] += sz[u];
}
}
int getC(int v, int P, int mx)
{
for (auto [u, w] : g[v])
{
if (u == P || dead[u] || sz[u] <= mx)
{
continue;
}
return getC(u, v, mx);
}
return v;
}
void getD(int v, int P, int D, int lvl, bool B, vector <int> &changed, int &limit)
{
if (D > limit)
{
return;
}
if (B)
{
if (mne[limit - D] != INT_MAX)
{
mncnt = min(mncnt, lvl + mne[limit - D]);
}
}
else
{
mne[D] = min(mne[D], lvl);
changed.push_back(D);
}
for (auto [u, w] : g[v])
{
if (u == P || dead[u])
{
continue;
}
getD(u, v, D + w, lvl + 1, B, changed, limit);
}
}
void decomp(int v, int &limit)
{
DFS(v, -1);
int c = getC(v, -1, sz[v] / 2);
dead[c] = true;
vector <int> changed;
for (auto [u, w] : g[c])
{
if (dead[u])
{
continue;
}
getD(u, c, w, 1, true, changed, limit);
getD(u, c, w, 1, false, changed, limit);
}
for (auto x : changed)
{
mne[x] = INT_MAX;
}
for (auto [u, w] : g[c])
{
if (dead[u])
{
continue;
}
decomp(u, limit);
}
}
};
// globals
// variables
int n, K;
// iterators
int i;
// notes
/*
My favorite anime is One Piece(obviously)
My oshi(Yes, I have an oshi, deal with it) is Kamil_Tsubaki
-stuff you should look for-
* int overflow, array bounds
* special cases (n=1?)
* do something instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
continue - skip the rest in the loop
*/
int best_path(int N, int K, int H[][2], int L[]) {
graph G;
G.prep(N, K);
// return 0;
for (int i = 0; i < N - 1; i++) {
const int &u = H[i][0], &v = H[i][1], &w = L[i];
G.adde(u, v, w);
}
G.decomp(1, K);
return (G.mncnt == INT_MAX ? -1 : G.mncnt);
}
int GCD(int A, int B)
{
if (!A)
{
return B;
}
return GCD(B % A, A);
}
int LCM(int A, int B)
{
return A * B / GCD(A, B);
}
int power(int base, int exponent)
{
int res = 1;
while (exponent)
{
if (exponent & 1)
{
res *= base;
}
base *= base;
exponent >>= 1;
}
return res;
}
/*
$$$$$$$$\ $$$$$$$$\
$$ _____|\____$$ |
$$ | $$ /
$$$$$\ $$ /
$$ __| $$ /
$$ | $$ /
$$$$$$$$\ $$$$$$$$\
\________|\________|
*/
```