| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 488634 | ssense | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "race.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
vector<vector<pair<int, int>>> adj;
int n_glob;
int k_glob;
vint size_sub;
vint del;
int calc(int u, int par)
{
int children = 1;
for(auto v : adj[u])
{
if(del[v.fr] == 0 && (par == -1 || v.fr != par))
{
children+=calc(v.fr, u);
}
}
size_sub[u] = children;
return children;
}
int find_centroid(int u, int size, int par)
{
for(auto v : adj[u])
{
if(v.fr != par && del[v.fr] == 0 && size_sub[v.fr] > size)
{
return find_centroid(v.fr, size, u);
}
}
return u;
}
int ans = MX+1000;
map<int, int> cnt;
void dfs(int u, int par, int weight, int type, int depth)
{
if(weight > k_glob)
{
return;
}
if(type == 0)
{
if(cnt.count(k_glob - weight))
{
ans = min(ans, cnt[k_glob - weight] + depth);
}
}
else{
if(!cnt.count(weight))cnt[weight] = depth;
else cnt[weight] = min(cnt[weight], depth);
}
for(auto x: adj[u]){
int v = x.first, w = x.second;
if(v == par || del[v])continue;
dfs(v, u, weight + w, type, depth + 1);
}
}
void assign(int u)
{
calc(u, -1);
int centroid = find_centroid(u, size_sub[u] / 2, -1);
cnt.clear();
cnt[0] = 0;
del[centroid] = 1;
for(auto x : adj[centroid])
{
int v = x.first, w = x.second;
if(del[v])continue;
dfs(v, -1, w, 0, 1);
dfs(v, -1, w, 1, 1);
}
for(auto x : adj[u])
{
if(del[x.fr] == 0)
{
assign(x.fr);
}
}
}
int best_path(int n, int k, int h[][2],int l[])
{
ans = MX+1000;
adj.clear();
n_glob = n;
k_glob = k;
for(int i = 0; i <= n; i++)
{
vector<pair<int, int>> cop;
adj.pb(cop);
}
for(int i = 0; i < n-1; i++)
{
adj[h[i][0]].pb({h[i][1], l[i]});
adj[h[i][1]].pb({h[i][0], l[i]});
}
size_sub.clear();
del.clear();
size_sub = vint(n+1);
del = vint(n+1);
assign(0);
if(ans == MX+1000)
{
return -1;
}
return ans;
}
int32_t main(){
startt
int n, k;
cin >> n >> k;
int h[n-1][2], l[n-1];
for(int i = 0; i < n-1; i++)
{
cin >> h[i][0] >> h[i][1];
}
for(int i = 0; i < n-1; i++)
{
cin >> l[i];
}
cout << best_path(n, k, h, l) << endl;
}
/*
3 3
0 1
0 2
1 1
4 3
0 1
1 2
1 3
1 2 4
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3 4 5 4 6 3 2 5 6 7
6 4
0 1
1 2
2 3
3 4
4 5
3 2 1 1 2
*/