| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1087797 | nmts | 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 file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout);
#define faster ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define fi first
#define se second
#define mii map< int , int>
#define reset(a,val) memset(a ,val , sizeof(a) )
#define endl '\n'
#define ll long long
#define int ll
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20 ;
template <class T> inline T sqr(T x) { return x * x; };
template <class T> inline int Power(T x, int y)
{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }
template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
inline int gcd(int x, int y)
{ return y ? gcd(y , x % y) : x;}
inline int lcm(int x, int y) { return x * y / gcd(x, y); }
using namespace std;
int n;
int ans = INF;
vector<pii> edges[maxn];
int k;
int cnt[maxn];
struct CD{
int sz[maxn];
bool del[maxn];
int dfs(int u , int p)
{
sz[u] = 1;
for (auto&[v , w] : edges[u])
if (v != p && del[v] == 0)
sz[u] += dfs(v , u);
return sz[u];
}
int find_centroid(int u , int p , int total)
{
for (auto&[v , w] : edges[u])
if (v != p && del[v] == 0 && sz[v] > total / 2)
return find_centroid(v ,u , total);
return u;
}
void calc(int u , int p, int l , int h , int t)
{
if (l > k) return;
if (t == 0)
{
minimize(ans , cnt[k - l] + h);
// cout << l << " " << cnt[k - l] + h << endl;
}
else if (t == 1) cnt[l] = min(cnt[l] , h);
else cnt[l] = INF + INF;
for (auto&[v , w]: edges[u])
if (v != p && del[v] == 0)
calc(v , u , l + w , h + 1 , t);
}
void decompose(int u )
{
u = find_centroid(u , 0 , dfs(u , 0));
del[u] = 1;
// cerr << u << endl;
for (auto&[v , w] : edges[u])
if (del[v] == 0)
{
calc(v , u , w , 1 , 0);
calc(v , u , w , 1 , 1);
}
for (auto&[v ,w] : edges[u])
if (del[v] == 0)
calc(v , u , w , 1 , -1);
for (auto&[v , w]: edges[u] )
if (del[v] == 0)
{
decompose(v);
}
}
} cd;
// void solve()
// {
// cin >> n >> k;
// for (int i = 1 ; i < n ; ++i)
// {
// int u , v , w; cin >> u >> v >> w;
// ++u , ++v;
// edges[u].push_back({v , w});
// edges[v].push_back({u , w});
// }
// memset(cnt , INF + INF , sizeof cnt);
// cnt[0] = 0;
// cd.decompose(1);
// cout << (ans >= INF ? -1 : ans) << endl;
// }
int best_path(int _n, int _k, int H[][2], int l[])
{
n = _n;
k = _k;
memset(cnt , INF + INF , sizeof cnt);
cnt[0] = 0;
for (int i = 0; i < n - 1; i++)
{
int w = l[i];
int u = H[i][0] + 1, v = H[i][1] + 1;
edges[u].push_back({v, w});
edges[v].push_back({u, w});
}
cd.decompose(1);
return (ans >= INF ? -1 : ans);
}
// int32_t main()
// {
// faster;
// // file("txt");
// // int t ; cin >> t ; while (t--)
// solve();
// return 0;
// }