| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 905078 | a_l_i_r_e_z_a | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// In the name of God
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())
const int maxn = 2e5 + 5, maxk = 1e6 + 5;
const int inf = 1e9 + 7;
ll n, k, ans = inf;
vector<pll> adj[maxn];
map<ll, ll> mn[maxn];
void dfs(int v = 0, int h = 0, ll d = 0, int p = -1){
mn[v].insert(mp(d, h));
for(auto [u, w]: adj[v]){
if(u == p) continue;
dfs(u, h + 1, d + w, v);
if(mn[u].size() > mn[v].size()) swap(mn[u], mn[v]);
for(auto w: mn[u]){
ll x = k + 2 * d - w.F;
auto it = mn[v].find(x);
if(it != mn[v].end()) smin(ans, w.S + (*it).S - 2 * h);
}
for(auto w: mn[u]){
auto it = mn[v].find(w.F);
if(it != mn[v].end()) smin((*it).S, w.S);
else mn[v].insert(w);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
fill(mn, mn + maxk, inf);
for(int i = 0; i < n - 1; i++){
int u = H[i][0], v = H[i][1], w = L[i];
adj[u].pb(mp(v, w));
adj[v].pb(mp(u, w));
}
dfs();
return (ans >= inf ? -1 : ans);
}
// int32_t main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// cin >> n >> k;
// for(int i = 0; i < n - 1; i++){
// int u, v, w; cin >> u >> v >> w;
// adj[u].pb(mp(v, w));
// adj[v].pb(mp(u, w));
// }
// dfs();
// cout << (ans >= inf ? -1 : ans) << '\n';
// return 0;
// }