| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1080913 | duduFreire | 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.
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(int i=(int)(a);i < (int)(b);i++)
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi>
#define sz(x) ((int)(x).size())
#ifdef LOCAL
#define debug(var) cerr << #var << ": " << var << endl
#else
#define debug(var)
#endif
using namespace std;
template<class T, class U> auto &operator>>(istream &is, pair<T, U> &p) { return is >> p.first >> p.second; }
template<class T, class U> auto &operator<<(ostream &os, pair<T, U> const& p) { return os << '{' << p.first << ' ' << p.second << '}'; }
const auto ES = "", SEP = " ";
template<class T> auto &operator>>(istream& is, vector<T> &c) { for (auto &x : c) is >> x; return is; }
template<class T> auto &operator<<(ostream& os, vector<T> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
template<class T> auto &operator<<(ostream& os, set<T> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
template<class T> auto &operator<<(ostream& os, multiset<T> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
template<class T> auto &operator<<(ostream& os, unordered_set<T> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
template<class T> auto &operator<<(ostream& os, deque<T> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
template<class K, class V> auto &operator<<(ostream& os, map<K,V> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
template<class K, class V> auto &operator<<(ostream& os, unordered_map<K,V> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
int ceil(int a, int b) {
return (a+b-1)/b;
}
constexpr int MAX=2e5;
constexpr int MOD=1e9+7;
constexpr int oo=0x3f3f3f3f3f3f3f3f;
/*
*/
int k;
struct Centroid {
vector<vector<pii>> g;
int rt, n;
vi rmv, ssz, par;
int ans=oo;
Centroid(vector<vector<pii>> ag, int art) : g(ag), rt(art), n(g.size()), rmv(n,0), ssz(n,0), par(n,0) {
centroid_tree(art);
}
int sizes(int a, int p=-1) {
int ans=1;
for(auto&[b,w]:g[a]) {
if (b == p or rmv[b]) continue;
ans+=sizes(b,a);
}
return ssz[a]=ans;
}
void calcdists(int a, int d, int p, vi& dists) {
dists[d]++;
for(auto&[b,w] : g[a]) {
if (rmv[b] or b==p) continue;
calcdists(b, d+1, a,dists);
}
}
int centroid(int a, int tsize, int p=-1) {
for(auto&[b,w]:g[a]) {
if (rmv[b] or b==p) continue;
if (ssz[b] * 2 > tsize) return centroid(b,tsize, a);
}
return a;
}
void centroid_tree(int a, int p=-1) {
int c=centroid(a, sizes(a));
rmv[c]=true;
par[c]=p;
solvesub(c);
for(auto&[b,w] : g[c]) {
if (rmv[b]) continue;
centroid_tree(b, c);
}
}
// do not visit removed guys (if rmv[b] continue)
void solvesub(int a) {
map<int,int> best, rbest;
auto dfs=[&](auto self, int a, int sum, int h, int p) -> void {
if (sum <= k) {
if (!rbest.count(sum) or rbest[sum] > h) rbest[sum]=h;
}
for (auto [b,w] : g[a]) if (!rmv[b] and b!=p) {
self(self,b,sum+w,h+1,a);
}
};
for (auto& [b,w] : g[a]) if (!rmv[b]) {
dfs(dfs, b, w, 1, a);
map<int,int> nbest;
for (auto [val, h] : rbest) {
if (best.count(k-val)) {
ans=min(ans, best[k-val]+h);
}
if (!best.count(val) or best[val] > h) nbest[val]=h;
}
for (auto [val, h] : nbest) best[val]=h;
map<int,int> gbg; swap(rbest, gbg);
}
}
};
int best_path(int n, int ak, int h[][2], int l[]) {
k=ak;
vector<vector<pii>> g(n);
rep(i,0,n-1) {
g[h[i][0]].eb(h[i][1],l[i]);
g[h[i][1]].eb(h[i][0],l[i]);
}
Centroid centroid(g, 0);
return centroid.ans == oo ? -1 : centroid.ans;
}