| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 349002 | Killer2501 | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb push_back
#define task "sequence"
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define fi first
#define se second
using ll = long long;
const long long mod = 1e15+7;
const ll N = 2e5 + 5;
const int base = 350;
using ull = unsigned long long;
using namespace std;
ll n, m, t, k, T, a[N], cnt, ans, u, tong, v, b[N], c[N];
map<ll, ll> mp[N];
vector<pll> kq, adj[N];
void dfs(ll u, ll p, ll hi, ll we)
{
mp[u][we] = hi;
for(pll v : adj[u])
{
if(v.fi == p)continue;
dfs(v.fi, u, hi+1, we+v.se);
if(mp[u].size() < mp[v.fi].size())swap(mp[u], mp[v.fi]);
for(pll x : mp[v.fi])
{
if(mp[u].count(we*2+m-x.fi))ans = min(ans, x.se + mp[u][we*2+m-x.fi] - 2 * hi);
}
for(pll x : mp[v.fi])
{
//if(v.fi == 2)cout << x.fi + v.se<<'\n';
if(!mp[u].count(x.fi) || mp[u][x.fi] > x.se)
{
mp[u][x.fi] = x.se;
if(x.fi== m)ans = min(ans, x.se);
}
}
//cout <<u<<" "<< v.fi<<'\n';
}
//cout << u << '\n';
//for(pll x : mp[u])cout << x.fi <<" "<<x.se<<'\n';
}
int best_path(ll n, ll m, ll h[][2], ll l[])
{
//cin >> n >> m;
for(int i = 0; i < n-1; i ++)
{
//cin >> a[i] >> b[i];
a[i] = h[i][0];
b[i] = h[i][1];
c[i] = l[i];
}
for(int i = 0; i < n-1; i ++)
{
//cin >> k;
adj[a[i]].pb({b[i], c[i]});
adj[b[i]].pb({a[i], c[i]});
//cout << a[i] <<" "<<b[i] <<" "<<k<<'\n';
}
ans = mod;
dfs(0, 0, 0, 0);
if(ans == mod)ans = -1;
return ans;
}