| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1024214 | tien_07 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define ms(a,n) memset(a,n,sizeof(a))
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
//Bit
#define MASK(x) (1ll<<(x))
#define BIT(mask, i) (((mask) >> (i))&1)
#define SET_ON(x,i) ((x) | MASK(i))
#define SET_OFF(x,i) ((x) & ~MASK(i))
#define c_bit(i) __builtin_popcountll(i)
#define TASK "test"
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<ll,ll> ii;
typedef pair<int,ii> iii;
typedef pair<ii,ii> iv;
typedef vector<ll> vll;
typedef vector<int> vi;
inline ll gcd(ll a, ll b){return b==0 ? a : gcd(b,a%b);}
inline ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
const ld PI = 3.141592653589793238462643383279502884L;
const int MOD = 998244353;
const ll LINF = 1e18;
const int INF = 1e9;
const int N = 2e5+5;
int n,k, H[N][2], L[N], ans[N];
vector<ii> g[N];
map<ll,int> mp[N];
void dfs(int u, int p){
mp[u][0] = 0;
for(auto &[v,w] : g[u]){
if(v==p) continue;
dfs(v,u);
for(auto &[len, cnt] : mp[v]){
if(len+w>k) continue;
if(mp[u].count(k-len-w)) ans[u] = min(ans[u], mp[u][k-len-w] + cnt+1);
}
for(auto &[len, cnt] : mp[v]){
if(len+w>k) continue;
if(mp[u].count(len+w)) mp[u][len+w] = min(mp[u][len+w], cnt+1);
else mp[u][len+w] = cnt+1;
}
}
}
void solve(){
cin >> n >> k;
FOR(i,1,n-1){
int u,v; cin >> u >> v;
H[i][0] = ++u; H[i][1] = ++v;
}
FOR(i,1,n-1) cin >> L[i];
FOR(i,1,n-1){
g[H[i][0]].push_back({H[i][1],L[i]});
g[H[i][1]].push_back({H[i][0],L[i]});
}
FOR(i,1,n) ans[i] = INF;
dfs(1,-1);
int tmp = *min_element(ans+1,ans+n+1);
cout << (tmp==INF ? -1 : tmp);
}
int main(){
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
int tc = 1; //cin >> tc;
while(tc--) solve();
return 0;
}