| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1080944 |
2024-08-29T16:13:27 Z |
duduFreire |
Race (IOI11_race) |
C++17 |
|
1 ms |
440 KB |
#include <bits/stdc++.h>
#define ll 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(ll i=(ll)(a);i < (ll)(b);i++)
#define pii pair<ll, ll>
#define vi vector<ll>
#define vvi vector<vi>
#define sz(x) ((ll)(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; }
ll ceil(ll a, ll b) {
return (a+b-1)/b;
}
constexpr ll MAX=2e5;
constexpr ll MOD=1e9+7;
constexpr ll oo=0x3f3f3f3f3f3f3f3f;
/*
*/
ll k;
struct Centroid {
vector<vector<pii>> g;
ll rt, n;
vi rmv, ssz, par;
ll ans=oo;
Centroid(vector<vector<pii>> ag, ll art) : g(ag), rt(art), n(g.size()), rmv(n,0), ssz(n,0), par(n,0) {
centroid_tree(art);
}
ll sizes(ll a, ll p=-1) {
ll 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(ll a, ll d, ll p, vi& dists) {
dists[d]++;
for(auto&[b,w] : g[a]) {
if (rmv[b] or b==p) continue;
calcdists(b, d+1, a,dists);
}
}
ll centroid(ll a, ll tsize, ll 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(ll a, ll p=-1) {
ll 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(ll a) {
map<ll,ll> best, rbest;
auto dfs=[&](auto self, ll a, ll sum, ll h, ll 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);
for (auto [val, h] : rbest) {
if (best.count(k-val)) {
ans=min(ans, best[k-val]+h);
}
}
for (auto [val, h] : rbest)
if (!best.count(val) or best[val] > h) best[val]=h;
map<ll,ll> 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
440 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
440 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
440 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
440 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
