| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 666374 | si_jo | Race (IOI11_race) | C++14 | 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 "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define pbds tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
#define ll long long
// #define int ll
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define all(x) (x).begin(), (x).end()
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define sz(x) (int)((x).size())
#define fr first
#define sc second
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define rep(i,a,b) for(int i = a; i < b; i++)
#define irep(i, a, b) for(int i = a; i > b; i--)
#define mem1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define clz __builtin_clzll //leading zeroes
#define ctz __builtin_ctzll //trailing zeroes
#define ppc __builtin_popcountll
#define nl cout << '\n'
template<typename T>
istream &operator>>(istream &in, vector<T>& v){
for(int i = 0; i < v.size(); i++)
in >> v[i];
return in;
}
template<typename T>
ostream &operator<<(ostream &out, vector<T>& v){
for(int i = 0; i < v.size(); i++)
out << v[i] << " ";
return out;
}
template<typename T1, typename T2>istream& operator>>(istream& in, pair<T1, T2>& p){ in >> p.fr >> p.sc; return in; }
template<typename T1, typename T2>ostream& operator<<(ostream& out, pair<T1, T2>& p){ out << p.fr << " " << p.sc << " "; return out; }
const ll INF = 1e18;
const int32_t M = 1e9 + 7;
const int32_t MM = 998244353;
const int MAX = numeric_limits<int>::max();
const int MIN = numeric_limits<int>::min();
const int N = 0;
int n, ans, k;
vi s, d, undo;
map<pii, int> wt;
void getsize(int cur, int par, vector<set<int>>& adj){
s[cur] = 1;
for(int a : adj[cur]) if(a != par){
getsize(a, cur, adj);
s[cur] += s[a];
}
}
int centre(int cur, int par, vector<set<int>>& adj, int tot){
for(int a : adj[cur]) if(a != par && s[a] > tot / 2) return centre(a, cur, adj, tot);
return cur;
}
void count(int cur, int par, vector<set<int>>& adj, bool f, int depth, int len){
if(len > k) return;
if(f) d[len] = min(d[len], depth);
else ans = min(ans, depth + d[k - len]);
for(int a : adj[cur]) if(a != par) count(a, cur, adj, f, depth + 1, len + wt[{a, cur}]);
}
void centroid(int cur, int par, vector<set<int>>& adj){
getsize(cur, par, adj);
int c = centre(cur, par, adj, s[cur]);
for(int a : adj[c]){
count(a, c, adj, 0, 1, wt[{a, c}]);
count(a, c, adj, 1, 1, wt[{a, c}]);
}
ans = min(ans, d[k]);
for(int i : undo) d[i] = 1e9;
undo.clear();
for(int a : adj[c]){
adj[a].erase(c);
centroid(a, c, adj);
}
}
int best_path(int N, int K, int[][2] H, int* L){
n = N; k = K;
s.resize(n + 1); d.assign(k + 1, 1e9);
ans = n;
vector<set<int>> adj(n + 1);
rep(i, 0, n - 1){
int u = H[i][0] + 1, v = H[i][1] + 1;
adj[u].insert(v); adj[v].insert(u);
wt[{u, v}] = wt[{v, u}] = L[i];
}
centroid(1, 0, adj);
return (ans == n ? -1 : ans);
}