| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 720162 | marvinthang | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/******************************
* author : @marvinthang *
* date : 15 / 01 / 2022 *
******************************/
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define superspeed ios_base::sync_with_stdio(false); cin.tie(nullptr); //cout.tie(nullptr);
#define file(name) if (fopen (name".inp", "r") ) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
#define LOCAL_DEBUG
#define REP(i, a, b) for (__typeof(a) i = (a) - ((a) > (b)); i != (b) - ((a) > (b)); i += ((a) > (b) ? -1 : 1))
#define FOR(i, a, b) for (__typeof(a) i = (a); i != (b) + ((a) > (b) ? -1 : 1); i += ((a) > (b) ? -1 : 1))
#ifdef LOCAL_DEBUG
#define DEBUG(name) freopen(name".out", "w", stderr);
#define db(val) '[' << #val << " = " << (val) << "] "
#define CONCAT(x, y) x##y
#define clog cerr << setw(__db_level * 2) << setfill(' ') << "" << setw(0)
#define Cerr cerr
#define DB() debug_block CONCAT(dbbl, __LINE__)
int __db_level = 0;
struct debug_block {
debug_block() { clog << "{\n"; ++__db_level; }
~debug_block() { --__db_level; clog << "}\n"; }
};
#else
#define DEBUG(name)
#define clog if (false) cerr
#define Cerr if (false) cerr
#define DB(...)
#endif
#define debug1(a) { clog << "L" << __LINE__ << ": " << #a << " = " << a << ";\n"; }
#define debug2(a, b) { clog << "L" << __LINE__ << ": " << #a << " = " << a << "; " << #b << " = " << b << ";\n"; }
#define debug3(a, b, c) { clog << "L" << __LINE__ << ": " << #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << ";\n"; }
#define debug4(a, b, c, d) { clog << "L" << __LINE__ << ": " << #a << " = " << a << ", " << #b << " = " << b << ", " << #c << " = " << c << ", " << #d << " = " << d << ";\n"; }
#define debugArr(A, a, b) { clog << "L" << __LINE__ << ": " << #A << " = {"; FOR(i, a, b) Cerr << A[i] << (i < b ? ", " : "}\n"); }
template <class U, class V> ostream & operator << (ostream& out, const pair<U, V> &p) { return out << '(' << p.first << ", " << p.second << ')'; }
template <class T> ostream & operator << (ostream &out, const vector<T> &vt) { out << '{'; for (size_t i = 0; i + 1 < vt.size(); i++) out << vt[i] << ", "; if (!vt.empty()) out << vt.back(); return out << '}'; }
void minimize(int &a, int b) { if (a > b) a = b; }
const int MOD = 1e9 + 7;
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {0, 1, 0, -1, 0}; // {0, 1, 1, -1, -1, 1, 0, -1, 0};
const long long oo = 1e18;
const int MAX = 2e5 + 5;
int N, K;
vector <pair <int, int>> adj[MAX];
int minPath[MAX * 10], newPath[MAX * 5], res = 1e9;
vector <int> save, save2;
bool used[MAX];
void calc(int u, int par, int depth, int weight) {
if (weight > K) return;
res = min(res, minPath[K - weight] + depth);
newPath[weight] = min(newPath[weight], depth);
save.push_back(weight);
save2.push_back(weight);
for (pair <int, int> &x: adj[u]) {
int v = x.second, w = x.first;
if (v == par || used[v]) continue;
calc(v, u, depth + 1, weight + w);
}
}
int sizes[MAX];
int calcSize(int u, int par) {
sizes[u] = 1;
for (pair <int, int> &x: adj[u]) {
int v = x.second;
if (v == par || used[v]) continue;
sizes[u] += calcSize(v, u);
}
return sizes[u];
}
int findCentroid(int u, int par, int n) {
for (pair <int, int> &x: adj[u]) {
int v = x.second;
if (v == par || used[v]) continue;
if (sizes[v] > n / 2) return findCentroid(v, u, n);
}
return u;
}
void solve(int u) {
int n = calcSize(u, 0);
int centroid = findCentroid(u, 0, n);
used[centroid] = true;
save.clear();
for (pair <int, int> &x: adj[centroid]) {
int v = x.second, w = x.first;
if (used[v]) continue;
calc(v, centroid, 1, w);
for (int &x: save2) {
minPath[x] = min(minPath[x], newPath[x]);
newPath[x] = N + 1;
}
save2.clear();
}
res = min(res, minPath[K]);
for (int &x: save) minPath[x] = N + 1;
for (pair <int, int> &x: adj[centroid]) {
int v = x.second;
if (!used[v]) solve(v);
}
}
int best_path(int n, int k, int h[][2], int l[])
superspeed;
N = n; k = K;
for (int i = 0; i < N - 1; ++i) {
int u = h[i][0], v = h[i][1], w = l[i];
++u; ++v;
adj[u].push_back( make_pair(w, v) );
adj[v].push_back( make_pair(w, u) );
}
fill(minPath, minPath + 1 + K, N + 1);
fill(newPath, newPath + 1 + K, N + 1);
solve(1);
if (res > N) res = -1;
return res;
}