| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1119860 | btninh | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define N 100005
#define pb push_back
#define mod 1000000007
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int,int>
#define INF 1e18
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, a, b) for(int i = a; i >= b; --i)
using namespace std;
int n, k, sz[N], ans = INF;
bool vis[N];
map<int,int> cnt;
vector<pii> g[N];
int dfs(int u, int p = -1)
{
sz[u] = 1;
for(auto [v, w] : g[u])
{
if (v != p && !vis[v])
{
sz[u] += dfs(v, u);
}
}
return sz[u];
}
int centroid(int u, int p, int len)
{
for(auto [v, w] : g[u])
{
if (v != p && !vis[v] && sz[v] > len / 2)
return centroid(v, u, len);
}
return u;
}
void calc(int u, int p, bool t, int sum, int d = 1)
{
if (t == 0)
{
if (!cnt[sum])
cnt[sum] = d;
else
cnt[sum] = min(cnt[sum], d);
}
else{
if (cnt[k - sum])
ans = min(ans, d + cnt[k - sum]);
}
for(auto [v, w] : g[u])
{
if (v != p && !vis[v])
{
calc(v, u, t, sum + w, d + 1);
}
}
}
void solve(int u)
{
int c = centroid(u, -1, dfs(u));
vis[c] = true;
for(auto [v, w] : g[c])
{
if (!vis[v])
{
calc(v, c, 0, w);
calc(v, c, 1, w);
}
}
for(auto [v, w] : g[c])
{
if (!vis[v]) solve(v);
}
}
void Proc()
{
cin >> n >> k;
vector<pii> E;
FOR(i, 1, n - 1)
{
int u, v;
cin >> u >> v;
++u; ++v;
E.pb({u, v});
}
for(int i = 0; i < n - 1; ++i)
{
int l; cin >> l;
int u = E[i].fi, v = E[i].se;
g[u].pb({v, l});
g[v].pb({u, l});
}
cnt[0] = 0;
solve(1);
cout << (ans != INF ? ans : -1);
}
int32_t main() {
/*if(fopen("test.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}*/
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; T = 1;
//cin >> T;
while (T--) Proc();
}